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

Операции над битами

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

Сравните поразрядно: 1100 и 1010. У & единица остаётся только там, где в обоих числах единицы (старший разряд) → 1000. У | единица там, где хоть в одном → 1110. У ^ — где биты разные → 0110.

Сдвиги — умножение и деление на степени двойки

Сдвиг влево x << 1 дописывает справа ноль — это удвоение. Сдвиг вправо x >> 1 отбрасывает правый бит — это целочисленное деление на 2. Сдвиг на n позиций умножает или делит на 2ⁿ.

Напечатается 42 и 0. Двойной XOR с одним числом отменяет сам себя (x ^ 7 ^ 7 = x), а число, поксоренное с собой, даёт 0. На этом свойстве построена классическая задача «найти единственный неповторяющийся элемент».

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

Ошибка. Перепутать битовые &, | с логическими and, or. 5 & 3 работает с битами (даёт 1), а 5 and 3 — это логика (даёт 3). Запустите код и сравните результаты, чтобы прочувствовать разницу.