10.1 Представление чисел в битах

Внутри программы все данные хранятся в виде битов — то есть нулей и единиц. Поэтому, чтобы уверенно пользоваться побитовыми операциями, полезно понимать, как именно целые числа записываются в памяти компьютера.

В программировании целое число из n бит хранится как двоичная запись длины n. Например, тип int в C++ обычно занимает 32 бита. Это означает, что каждое значение типа int представляется последовательностью из 32 нулей и единиц.

Например, число 43 в двоичном виде выглядит так:

00000000000000000000000000101011

Биты принято нумеровать справа налево, начиная с нуля. Если двоичная запись имеет вид

b_k ... b_2 b_1 b_0

то соответствующее ей число вычисляется по формуле:

\[ b_k 2^k + \dots + b_2 2^2 + b_1 2^1 + b_0 2^0. \]

Например, для числа 43 получаем:

\[ 1 \cdot 2^5 + 1 \cdot 2^3 + 1 \cdot 2^1 + 1 \cdot 2^0 = 32 + 8 + 2 + 1 = 43. \]

Знаковое и беззнаковое представление

Битовое представление числа может быть знаковым (signed) или беззнаковым (unsigned).

Обычно в задачах по программированию используется знаковое представление, где можно хранить и положительные, и отрицательные числа. Если число занимает n бит, то диапазон значений в знаковом формате таков:

\[ -2^{n-1} \dots 2^{n-1}-1. \]

Например, 32-битный int в C++ обычно может хранить числа от

\[ -2^{31} \text{ до } 2^{31}-1. \]

В знаковом представлении старший бит отвечает за знак числа:

• 0 — число неотрицательное;
• 1 — число отрицательное.

Для хранения отрицательных чисел обычно используется дополнительный код (two’s complement). Чтобы получить представление числа -x, нужно:

1. взять двоичную запись числа x;
2. инвертировать все биты;
3. прибавить 1.

Например, число -43 в 32-битном int записывается так:

11111111111111111111111111010101

Беззнаковые числа

В беззнаковом формате можно хранить только неотрицательные числа, зато верхняя граница становится больше. Если число занимает n бит, то диапазон будет таким:

\[ 0 \dots 2^n - 1. \]

Например, unsigned int в C++ обычно хранит значения от

\[ 0 \text{ до } 2^{32}-1. \]

Между знаковым и беззнаковым представлением есть полезная связь: число -x в знаковом формате соответствует числу 2^n - x в беззнаковом формате.

Например:

int x = -43;
unsigned int y = x;

cout << x << "\n"; // -43
cout << y << "\n"; // 4294967253

Здесь значение -43 интерпретируется как беззнаковое число 2^32 - 43.

Переполнение

Если число выходит за допустимые границы своего битового представления, происходит переполнение.

• В знаковом формате после числа 2^{n-1} - 1 идёт -2^{n-1}.
• В беззнаковом формате после числа 2^n - 1 идёт 0.

Например, для 32-битного int:

int x = 2147483647;
cout << x << "\n"; // 2147483647
x++;
cout << x << "\n"; // -2147483648

Изначально x = 2^{31} - 1 — это максимально возможное значение типа int. После увеличения на единицу происходит переход к числу -2^{31}.

Небольшой пример для интуиции

Посмотрим на 8-битное представление, чтобы увидеть идею компактнее.

Число 13 в 8 битах:

00001101

Число -13 в дополнительном коде:

1. инвертируем биты 00001101 → 11110010
2. прибавляем 1 → 11110011

Итак,

-13 = 11110011

Такой пример удобен, потому что на короткой записи хорошо видно, как устроено кодирование отрицательных чисел.

Что важно запомнить

• Любое целое число в памяти — это просто набор битов.
• Значение числа определяется тем, как мы интерпретируем эти биты.
• Один и тот же набор битов можно трактовать по-разному: как signed или как unsigned.
• Переполнение — это не «ошибка в воздухе», а переход к другому числу внутри фиксированного диапазона битов.

Это понимание особенно важно дальше, когда мы будем использовать побитовые операции, маски и представление множеств через биты.