Битовое представление чисел - Алгоритмика
Битовое представление чисел

Битовое представление чисел

автор Сергей Слотин
обновлено авг. 21, 2021
Все целые числа можно записать в двоичной системе счисления: $$ \begin{aligned} 5_{10} &= 101_2 = 4 + 1 \\ 42_{10} &= 101010_2 = 32 + 8 + 2 \\ 256_{10} &= 100000000_2 = 2^8 \end{aligned} $$

Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 8 (char), 16 (short), 32 (int) или 64 (long long) бит.

Эндианность

Единственная неоднозначность в таком формате возникает с порядком хранения битов — также называемый эндианностью. Зависимости от архитектуры он может быть разным:

  • При схеме little-endian сначала идут младшие биты. Например, число $42_{10}$ будет храниться так: $010101$.
  • При записи в формате big-endian сначала идут старшие биты. Все примеры из начала статьи даны в big-endian формате.

Хотя big-endian более естественный для понимания — на бумаге мы ровно так обычно и записываем бинарные числа — по разным причинам на большинстве современных процессоров по умолчанию используется little endian.

Иными словами, «$i$-тый бит» означает «$i$-тый младший» или «$i$-тый справа», но на бумаге мы ничего не инвертируем и записываем двоичные числа стандартным образом.

Битовые операции

Помимо арифметических операций, с числами можно делать и битовые, которые интерпретируют их просто как последовательность битов.

Сдвиги

Битовую запись числа можно «сдвигать» влево (x << y) или вправо (x >> y), что эквивалентно умножению или делению на степень двойки с округлением вниз.

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

Побитовые операции

Помимо &&, || и !, существуют их побитовые версии, которые применяют соответствующую логическую операцию к целым последовательностям битов: &, |, ~.

Также помимо них есть ещё операция исключающего «или» (XOR), которая записывается как ^.

Например:

  • $13$ & $7$ = $1101_2$ & $0111_2$ = $0101_2$ = $5$
  • $17$ | $10$ = $10001_2$ | $01010_2$ = $11011_2$ = $27$
  • $17$ ^ $9$ = $10001_2$ ^ $01001_2$ = $11000_2$ = $24$

Все побитовые операции тоже работают за один такт, вне зависимости от типа данных. Для больших не вмещающихся в один регистр битовых последовательностей существует битсет.

Маски

Бинарные последовательности можно поставить в соответствие подмножествам какого-то фиксированного множества: если на $i$-той позиции стоит единица, то значит $i$-тый элемент входит множество, а иначе не входит.

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

Выделить i-й бит числа

(x >> i) & 1 или x & (1 << i). Во втором случае результат будет либо 0, либо $2^i$.

Это часто используется для проверки, принадлежит ли $i$-тый элемент множеству:

if ((num >> i) & 1)
    cout << "YES";
else
    cout << "NO";

Напомним, что нумерация идет с младших бит и начинается с нуля.

Получить число, состоящее из k единиц

(1 << k) - 1, также известное как $(2^k-1)$ и соответствующее маске полного множества.

Инвертировать все биты числа

x = ~x

Добавить i-й элемент в множество

x |= (1 << i)

Удалить $i$-й элемент из множества

x &= ~(1 << i)

Удалить i-й элемент из множества, если он есть

x ^= (1 << i)

Также добавляет этот элемент, если его нет.

Знаковые числа

Целочисленные переменные делятся на два типа — знаковые (signed) и беззнаковые (unsigned).

Если сложить две unsigned int переменные, сумма которых превосходит $2^{32}$, произойдет переполнение: сумму нельзя будет представить точно, и поэтому вместо неё результатом будут только нижние 32 бит. Все операции с беззнаковыми числами как бы проходят по модулю какой-то степени двойки.

Знаковые же типы нужны для хранения значений, которые могут быть и отрицательными. Для этого нужно выделить один бит для хранение знака — отрицательное ли число или нет — немного пожертвовав верхней границей представимых чисел: теперь самое большое представимое число это $2^{31}-1$, а не $2^{32}-1$.

Инженеры, которые работают над процессорами, ещё более ленивые, чем программисты — это мотивировано не только стремлением к упрощению, но и экономией транзисторов. Поэтому когда в signed типах происходит переполнение, результат в битовом представлении считается так же, как и в случае с unsigned числами. Если мы хотим ничего не менять в плане того, как работают unsigned числа, представление отрицательных чисел должно быть таким, что число $-x$ как бы вычитается из большой степени двойки:

$$ \begin{aligned} -x = 2^{32} - x \end{aligned} $$

Несколько следствий:

  • Все неотрицательные числа записываются в точности как раньше.
  • У всех отрицательных чисел самый большой бит будет единичным.
  • Если прибавить к $2^{31}-1$ единицу, то результатом будет $-2^{31}$, представляемое как 10000000 (в целях изложения мы будем записывать 8 бит, хотя в int их 32).
  • Зная двоичную запись положительного числа x, запись -x можно получить как ~x + 1.
  • -1 записывается как ~1 + 1 = 11111110 + 00000001 = 11111111.
  • -42 записывается как ~42 + 1 = 11010101 + 00000001 = 11010110.
  • После -1 = 11111111 идет 0 = -1 + 1 = 11111111 + 00000001 = 00000000.

Упражнение. Каких чисел больше: положительных или отрицательных?

Осторожно. В стандарте C/C++ прописано, что переполнение знаковых переменных приводит к undefined behavior, поэтому полагаться на описанную логику переполнения нельзя, хотя равно это скорее всего и произойдет.

128-битные числа

Общих регистров размера больше 64 в процессорах нет, однако умножение и несколько смежных инструкций могут использовать два последовательных регистра как один большой. Это позволяет быстро перемножать два 64-битных числа и получать 128-битный результат, разделенный на нижние биты и верхние.

Это весьма специфичная операция, и поэтому в языках программирования нет полноценной поддержки 128-битных переменных. В C++ однако есть «костыль» — тип __int128_t — который фактически просто оборачивает пару из двух 64-битных регистров и поддерживает арифметические операции с ними.

__int128_t x = 1;
int64_t hi = x >> 64; // получить верхние 64 бит
int64_t lo = (int64_t) x; // получить нижние 64 бит

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