10.2 Побитовые операции¶
Побитовые операции позволяют работать с двоичным представлением чисел напрямую. В олимпиадном программировании это особенно полезно, когда нужно быстро проверять свойства числа, управлять отдельными битами или компактно хранить состояние.
Операция AND¶
Операция x & y оставляет единицы только в тех разрядах, где единицы стоят и в x, и в y.
Например:
10101 (21)
&11001 (25)
=10001 (17)
То есть 21 & 25 = 17.
Операция AND часто используется для проверки отдельных свойств числа.
Например, число x чётное тогда и только тогда, когда:
(x & 1) == 0
Если последний бит равен 0, число чётное. Если последний бит равен 1, число нечётное.
Более общий факт: число x делится на 2^k тогда и только тогда, когда
(x & ((1 << k) - 1)) == 0
Это означает, что все последние k битов равны нулю.
Операция OR¶
Операция x | y ставит единицу в тех разрядах, где единица есть хотя бы в одном из чисел.
Пример:
10101 (21)
|11001 (25)
=11101 (29)
То есть 21 | 25 = 29.
Эта операция удобна, когда нужно «включить» какие-то биты.
Операция XOR¶
Операция x ^ y ставит единицу в тех разрядах, где биты различаются.
Пример:
10101 (21)
^11001 (25)
=01100 (12)
То есть 21 ^ 25 = 12.
Операция XOR часто встречается в задачах на чётность, инварианты, хеширование состояний и поиск отличающихся битов.
Операция NOT¶
Операция ~x инвертирует все биты числа: нули превращаются в единицы, а единицы — в нули.
Для целых чисел в дополнительном коде выполняется полезная формула:
~x = -x - 1
Например:
~18 == -19
Важно помнить, что результат зависит от длины типа. Для 32-битного int число 18 выглядит так:
x = 18 00000000000000000000000000010010
~x = -19 11111111111111111111111111101101
Поэтому NOT надо использовать аккуратно: он меняет все биты, а не только значащие.
Побитовые сдвиги¶
Сдвиг влево¶
Операция x << k сдвигает биты числа влево на k позиций, дописывая справа нули.
Например:
13 = 1101
13 << 2 = 110100 = 52
То есть:
13 << 2 == 52
Обычно это соответствует умножению на 2^k.
Сдвиг вправо¶
Операция x >> k удаляет последние k битов.
Например:
54 = 110110
54 >> 2 = 1101 = 13
То есть:
54 >> 2 == 13
Обычно это соответствует целочисленному делению на 2^k.
Практические применения¶
Проверка k-го бита¶
Число вида 1 << k содержит единственную единицу в позиции k. Поэтому k-й бит числа x равен 1 тогда и только тогда, когда:
x & (1 << k)
не равно нулю.
Пример:
int x = 26; // 11010
int k = 3;
if (x & (1 << k)) {
cout << "Бит установлен\n";
}
Вывод битового представления¶
Следующий код печатает двоичную запись числа типа int:
for (int i = 31; i >= 0; i--) {
if (x & (1 << i)) cout << "1";
else cout << "0";
}
cout << "\n";
Установить бит в 1¶
x = x | (1 << k);
Сбросить бит в 0¶
x = x & ~(1 << k);
Инвертировать бит¶
x = x ^ (1 << k);
Эти три операции очень часто используются в битмасках.
Полезные приёмы¶
Убрать последний установленный бит¶
x = x & (x - 1);
Эта операция зануляет самый правый бит, равный 1.
Пример:
x = 40 = 101000
x - 1 = 39 = 100111
x & (x - 1) = 100000 = 32
Оставить только последний установленный бит¶
x = x & -x;
Пример:
x = 40 = 101000
-x в дополнительном коде
x & -x = 001000 = 8
Это полезно, например, в дереве Фенвика.
Сделать все биты справа от последней единицы равными 1¶
x = x | (x - 1);
Пример:
x = 40 = 101000
x - 1 = 100111
x | (x - 1) = 101111 = 47
Проверка, является ли число степенью двойки¶
Положительное число x является степенью двойки тогда и только тогда, когда
x & (x - 1)
равно нулю.
То есть:
if (x > 0 && (x & (x - 1)) == 0) {
cout << "Степень двойки\n";
}
Причина в том, что у степени двойки в двоичной записи ровно один установленный бит.
Встроенные функции g++¶
Компилятор g++ предоставляет удобные функции для работы с битами.
Количество нулей в начале числа¶
__builtin_clz(x)
Возвращает число ведущих нулей в записи int.
Количество нулей в конце числа¶
__builtin_ctz(x)
Возвращает число завершающих нулей.
Количество единиц¶
__builtin_popcount(x)
Возвращает число битов, равных 1.
Чётность числа единиц¶
__builtin_parity(x)
Возвращает 0, если единиц чётное количество, и 1, если нечётное.
Пример:
int x = 720; // 00000000000000000000001011010000
cout << __builtin_clz(x) << "\n";
cout << __builtin_ctz(x) << "\n";
cout << __builtin_popcount(x) << "\n";
cout << __builtin_parity(x) << "\n";
Для long long существуют версии с суффиксом ll:
__builtin_clzll(x)
__builtin_ctzll(x)
__builtin_popcountll(x)
__builtin_parityll(x)
Краткий итог¶
Побитовые операции особенно полезны в трёх случаях:
- когда нужно быстро проверять свойства числа;
- когда требуется управлять отдельными битами;
- когда состояния задачи удобно кодировать битовой маской.
Именно поэтому побитовые операции часто встречаются в задачах на множества, динамическое программирование, перебор подмножеств и оптимизацию по памяти.