Bit Manipulation: трюки с битами

Цели урока

• Понимать AND, OR, XOR, NOT и сдвиги
• Применять трюки: проверка степени 2, popcount, работа с битами
• Решать задачи с XOR (Single Number и вариации)
• Использовать битовые маски для множеств и DP

Предварительные знания

• Двоичная система счисления
• Базовое программирование

Битовые операции - язык процессора. Они самые быстрые и часто дают короткие решения.

• XOR-трюки: любимая тема интервьюеров FAANG
• Bitmask DP превращает экспоненциальные задачи в решаемые

HAKMEM и трюк Кернигана

Битовые трюки родом из эпохи, когда каждый такт процессора и каждый байт памяти были на счету. В 1972 году в MIT AI Lab появился знаменитый сборник памяток HAKMEM (AI Memo 239), куда Билл Госпер и коллеги собрали десятки хитрых приёмов работы с битами и арифметикой. Один из самых известных приёмов, подсчёт установленных битов через выражение n & (n - 1), которое за одну операцию убирает младший единичный бит, часто связывают с именем Брайана Кернигана. Эти приёмы до сих пор живут в низкоуровневом коде, криптографии и на собеседованиях.

Зачем нужны битовые операции?

Представь, что ты работаешь напрямую с **атомами информации**. Каждый бит - это 0 или 1, вкл/выкл, да/нет. Битовые операции позволяют манипулировать этими атомами напрямую, минуя все абстракции.

Битовые операции - это **самые быстрые операции** в компьютере. Они выполняются за 1 такт процессора, быстрее чем сложение, умножение или деление.

**Почему это важно на практике?**

1. **Экономия памяти**: вместо массива из 32 boolean (32 байта) можно использовать одно 32-битное число (4 байта). В 8 раз меньше!

2. **Скорость**: операции над 32 флагами за 1 такт вместо 32 отдельных проверок.

3. **Элегантность**: некоторые задачи имеют красивые битовые решения, которые кажутся магией.

**Метафора: пульт управления**

Представь пульт с 8 переключателями (тумблерами). Каждый может быть ON (1) или OFF (0). Состояние всего пульта - это 8-битное число. Например, если включены переключатели 0, 2 и 3:

Битовые операции позволяют: включать переключатели, выключать их, переключать, проверять состояние - и всё это за O(1).

Основные операции: AND, OR, XOR, NOT

Есть 4 базовые побитовые операции. Каждая работает с битами **по отдельности** - бит 0 одного числа с битом 0 другого, бит 1 с битом 1, и так далее.

**AND (&) - логическое И**

Результат = 1 только если **оба** бита = 1. Как охранник на входе: пропустит только если есть И билет, И документ.

**OR (|) - логическое ИЛИ**

Результат = 1 если **хотя бы один** бит = 1. Как выключатель света с двух мест: свет горит если любой из них включен.

**XOR (^) - исключающее ИЛИ**

Результат = 1 если биты **различаются**. У XOR самый интересный набор свойств среди битовых операций.

**NOT (~) - инверсия**

Переворачивает все биты: 0 → 1, 1 → 0.

Запомни главное: AND для проверки/обнуления битов, OR для установки битов, XOR для переключения и 'магии'.

Сдвиги: умножение и деление без умножения

**Сдвиг влево (<<)** - сдвигает все биты влево, справа добавляются нули. Это **умножение на степень двойки**.

Почему? Вспомни десятичную систему: 5 × 10 = 50 (добавили ноль справа). В двоичной: добавление нуля справа - умножение на 2.

**Сдвиг вправо (>>)** - сдвигает биты вправо, отбрасывая правые биты. Это **деление на степень двойки** (с округлением вниз).

Сдвиги в 10-100 раз быстрее обычного деления. Компиляторы автоматически заменяют n * 2 на n << 1.

**Создание маски: 1 << i**

Выражение `1 << i` создаёт число с единственной единицей на позиции i. Это 'маска' для работы с конкретным битом.

Практические трюки с битами

Теперь применим знания на практике. Вот самые полезные битовые паттерны.

**1. Проверка чётности: n & 1**

Последний бит (бит 0) определяет чётность числа. Если он 0 - число чётное, если 1 - нечётное.

**2. Проверка степени двойки: n & (n - 1) === 0**

Это один из самых красивых битовых трюков. Степени двойки имеют ровно один единичный бит. А n - 1 переворачивает все биты от этой единицы до конца:

**3. Работа с отдельными битами**

**4. Подсчёт единичных битов (popcount)**

Kernighan's algorithm делает ровно k итераций, где k - количество единичных битов. Для разреженных чисел это намного быстрее.

Магия XOR: задача Single Number

XOR обладает уникальными свойствами, которые делают его невероятно полезным для определённых задач.

**Три ключевых свойства XOR:**

**Классическая задача: Single Number (LeetCode #136)**

Дан массив, где все числа встречаются **дважды**, кроме одного уникального. Найти это уникальное число.

Наивное решение: HashMap для подсчёта - O(n) памяти. Но с XOR можно за O(1) памяти!

**Визуализация: почему пары исчезают**

**Другие применения XOR:**

XOR - это 'обратимая' операция. Если знаешь a ^ b = c, то можешь восстановить a = c ^ b или b = c ^ a. На этом строится XOR-шифрование.

Битовые маски: множество в одном числе

**Битовая маска** - это использование числа как **множества**. Каждый бит отвечает за один элемент: 1 = элемент есть, 0 = элемента нет.

**Пример: множество {0, 2, 3}**

**Операции над множествами через биты:**

**Практический пример: генерация всех подмножеств**

**Bitmask DP: TSP за O(n² × 2^n)**

Задача коммивояжёра обычно O(n!), но с битовыми масками можно сократить до O(n² × 2^n). Идея: dp[mask][i] = минимальный путь, посетив города в mask, закончив в городе i.

Bitmask работает для n ≤ 20-25 (2^25 ≈ 33M состояний). Для больших n нужны приближённые алгоритмы.

Итоги

• AND (&): для проверки и обнуления битов
• OR (|): для установки битов
• XOR (^) даёт ключевое свойство: a^a=0, a^0=a
• Сдвиги: быстрое умножение/деление на степени 2
• n & (n-1) убирает младший единичный бит
• Битовая маска: множество в одном числе

Связи с другими темами

Биты связаны с архитектурой компьютера и криптографией

• Архитектура CPU — Битовые операции - базовый уровень
• Криптография — XOR-шифрование
• Сжатие данных — Эффективное кодирование

Связанные уроки

• ds-24-bloom-filter — Bloom-фильтры устанавливают и проверяют отдельные биты
• alg-22-backtracking — Bitmask DP кодирует посещённые подмножества битами
• crypto-14-aes — Блочные шифры построены на битовых операциях
• dm-01 — Побитовые AND, OR, XOR реализуют булеву алгебру
• comp-01-intro