Битовые операции: трюки и задачи

Что такое битовые операции

Они работают с числами на уровне двоичного представления:

& — AND
| — OR
^ — XOR
~ — NOT
<< — сдвиг влево
>> — сдвиг вправо

Например, число 5 — это 101, а 3 — 011.

Популярные трюки

1. Проверка чётности

   n & 1

   Если результат 0 — число чётное, если 1 — нечётное.

2. Умножение и деление на 2

   n << 1  → умножить на 2
   n >> 1  → разделить на 2

   Работает быстро, но важно учитывать знаковые числа.

3. Проверка, является ли число степенью двойки

   n > 0 && (n & (n - 1)) == 0

   У степени двойки только один установленный бит.

4. Удаление последнего установленного бита

   n & (n - 1)

   Полезно для подсчёта количества единичных битов.

5. Получение последнего установленного бита

   n & -n

   Часто применяется в Fenwick Tree и битовых масках.

Где это реально применяют 🚀

• работа с флагами и правами доступа
• оптимизация памяти
• маски состояний в задачах на DP
• сжатие данных
• низкоуровневый код и драйверы
• обработка сетевых протоколов

Типовые задачи на собеседованиях

1. Найти число, которое встречается один раз, если остальные встречаются дважды.

   Решение: XOR всех элементов. Одинаковые числа взаимно уничтожаются.

2. Подсчитать количество единиц в числе.

   Можно циклом сдвигать число или использовать трюк:

   while (n) { n = n & (n - 1); count++; }

3. Поменять местами значения без третьей переменной.

   Через XOR это возможно, но в продакшене такой код хуже читается, поэтому чаще берут обычный temp.

Частые ошибки ⚠️

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

Когда битовые операции действительно полезны

Если нужна производительность, компактное хранение данных или решение алгоритмической задачи — это отличный инструмент. Но ради “красивого трюка” применять их не стоит: поддерживаемость кода важнее.