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

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

операция	запись	что делает
и	a & b	бит равен единице, если он есть у обоих
или	a | b	бит равен единице, если он есть хотя бы у одного
исключающее или	a ^ b	бит равен единице, если он есть ровно у одного
отрицание	~a	все биты переворачиваются
сдвиг влево	a << k	биты уезжают влево, справа приходят нули
сдвиг вправо	a >> k	биты уезжают вправо

Сдвиг влево на $k$ — это умножение на $2^k$, сдвиг вправо — деление с округлением вниз (для неотрицательных чисел). Но пользоваться сдвигом вместо умножения ради скорости не нужно: компилятор делает это сам, а читается хуже.

Отрицательные числа

Знаковые числа хранятся в дополнительном коде: старший бит означает знак, а $-x$ равно $\lnot x + 1$. Отсюда несколько следствий, о которых стоит помнить.

~0 равно $-1$, а не нулю и не единице. ~5 равно $-6$.

Сдвиг вправо отрицательного числа в C++ арифметический: слева приходят единицы, а не нули. То есть -8 >> 1 равно $-4$, а не огромному положительному числу.

Сдвиг влево знакового числа за пределы диапазона — неопределённое поведение. Для битовых манипуляций надёжнее беззнаковые типы.

Приоритеты

Самая частая ошибка в битовом коде — не в логике, а в скобках. В C++ приоритет битовых операций ниже, чем у сравнений:

if (a & 1 == 0)          // это a & (1 == 0), то есть a & 0, то есть всегда 0
if ((a & 1) == 0)        // а вот так правильно

Порядок такой: сначала сдвиги, потом сравнения, потом &, потом ^, потом |. Проще не помнить, а ставить скобки — в битовом коде их лишними не бывает.

Ширина типа

Второе классическое место: 1 << 40. Единица здесь имеет тип int, сдвиг происходит в 32 битах, и результат не определён. Нужно 1LL << 40 или 1ULL << 40.

Компилятор об этом обычно молчит, а на тестах поменьше всё работает. Правило простое: если сдвиг может быть больше 30, пишите суффикс.

Смежное

• Биты и маски — как работать с отдельным битом;
• Битовые трюки — короткие идиомы, которые стоит знать;
• Маска как множество — главное применение.