Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 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$ как бы вычитается из большой степени двойки:
Несколько следствий:
- Все неотрицательные числа записываются в точности как раньше.
- У всех отрицательных чисел самый большой бит будет единичным.
- Если прибавить к $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 бит
Базовые арифметические операции с ним чуть медленнее, его нельзя напрямую печатать, и деление и прочие сложные операции будут вызывать отдельную библиотеку и поэтому работать очень долго, однако в некоторых ситуациях он оказывается очень полезен.