Bit Manipulation

Битовые операции — это прямая работа с двоичным представлением чисел. Каждое 32-битное целое — это набор из 32 булевых флагов, и битовые операции позволяют обрабатывать все биты параллельно за O(1). В мире высоконагруженных систем и embedded programming это критически важно: меньше памяти (один int вместо 32 bool), быстрее работа (на уровне процессора), элегантные решения для задач на множества и подмножества. На собеседованиях битовые трюки показывают глубину понимания low-level деталей.

Когда применять

Уникальный элемент среди дубликатов → XOR всех элементов.
Подсчёт битов (popcount) → Brian Kernighan.
Генерация всех подмножеств → loop по маскам от 0 до 2ⁿ - 1.
Хеширование — XOR хешей для коммутативности.
Низкоуровневые оптимизации — умножение/деление на степень двойки через сдвиги.
Флаги и permissions — упаковка нескольких булевых полей в один int.
Bitmask DP для задач с n ≤ 20.

Идея: основные операции

Операция	Смысл
`&` (AND)	«Фильтр»: 1, если оба бита 1.
`\|` (OR)	«Объединение»: 1, если хотя бы один.
`^` (XOR)	«Переключатель»: 1, если биты разные.
`~` (NOT)	Инверсия всех битов.
`<<`	Left shift, умножение на 2ᵏ.
`>>`	Signed right shift, деление с сохранением знака.
`>>>`	Unsigned right shift (JS): заполняет нулями слева.

:::caution JS-специфика Битовые операции в JS приводят операнды к 32-битным signed int, результат — тоже signed. Для чисел больше 2³¹ или для unsigned — используй >>> 0 или BigInt. :::

Магические трюки

x & (x - 1) — сбрасывает самый правый 1-бит (используется в Brian Kernighan popcount и Fenwick tree).
x & -x — выделяет самый правый 1-бит (lowbit, основа Fenwick tree).
x > 0 && (x & (x - 1)) === 0 — проверка, что x — степень двойки.
x ^ x === 0, x ^ 0 === x — база для Single Number.
(x >> k) & 1 — читает k-й бит.
x | (1 << k) — устанавливает k-й бит в 1.
x & ~(1 << k) — сбрасывает k-й бит в 0.
x ^ (1 << k) — инвертирует k-й бит.

Реализация: Single Number

Задача: дан массив, где каждый элемент встречается дважды, кроме одного. Найти уникальный за O(n) время и O(1) память.

Подход: XOR коммутативен и ассоциативен, a ^ a = 0, a ^ 0 = a. Если XOR’им все элементы, парные сократятся в 0, останется единственный непарный.

function singleNumber(nums: number[]): number {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}

console.log(singleNumber([4, 1, 2, 1, 2])); // 4
console.log(singleNumber([2, 2, 1]));        // 1

Трассировка для `[4,1,2,1,2]`

result = 0
result ^= 4 → 0 ^ 4 = 4   (0100)
result ^= 1 → 4 ^ 1 = 5   (0101)
result ^= 2 → 5 ^ 2 = 7   (0111)
result ^= 1 → 7 ^ 1 = 6   (0110)
result ^= 2 → 6 ^ 2 = 4   (0100)
Ответ: 4

Почему: переставим — (4^1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4. Все пары сокращаются.

Реализация: Number of 1 Bits (popcount)

Метод Brian Kernighan: операция n & (n-1) сбрасывает самый правый 1-бит. Повторяем, пока n не станет 0. Количество итераций = количество 1-битов. Это быстрее наивного перебора всех 32 битов, потому что итераций столько, сколько единиц.

function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // сбрасываем самый правый 1-бит
    count++;
  }
  return count;
}

// Наивный для сравнения
function hammingWeightNaive(n: number): number {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) count++;
  }
  return count;
}

console.log(hammingWeight(11));  // 3 (1011)
console.log(hammingWeight(128)); // 1

Трассировка для n = 11 (1011)

n=1011, n-1=1010, n & (n-1) = 1010 → count=1
n=1010, n-1=1001, n & (n-1) = 1000 → count=2
n=1000, n-1=0111, n & (n-1) = 0000 → count=3
Ответ: 3

Почему n & (n-1) сбрасывает правый 1-бит: n-1 инвертирует все биты справа от правого 1 (включая его — превращает в 0). AND с n оставляет левые биты, а правый 1 и всё правее обнуляется.

Сложность

Single Number: O(n) время, O(1) память — оптимально.
Brian Kernighan popcount: O(k), где k — число 1-битов (≤ 32).
Subset enumeration: O(n · 2ⁿ) для всех подмножеств.

Дополнительные битовые трюки

Проверка чётности: n & 1 (1 если нечётное).
Степень двойки: n > 0 && (n & (n-1)) === 0.
Умножение/деление на 2ᵏ: n << k / n >> k.
Swap без temp: a^=b; b^=a; a^=b; (в современных языках не быстрее, но красиво).
Lowbit: n & -n — выделить самый правый 1-бит (Fenwick tree).
Subset enumeration маски: for (let sub = mask; sub > 0; sub = (sub - 1) & mask) — перебирает все подмножества mask за O(3ⁿ) суммарно.

Типичные ошибки и подводные камни

Перепутать & (битовый AND) и && (логический AND).
Забыть скобки: x & 1 == 0 неверно — == имеет приоритет выше &. Нужно (x & 1) === 0.
Использовать signed >> вместо >>> для unsigned.
Не учитывать 32-битное ограничение JS — для бо́льших чисел нужен BigInt.
Сдвиг на ≥ 32: в JS эквивалентен сдвигу на k % 32, легко получить «не то».
Отрицательные числа в two’s complement: ~x === -x - 1.

Edge cases для тестов: 0, 1, -1, 2³¹ - 1, -2³¹.

Follow-up вопросы

Single Number III: найти два уникальных числа среди дубликатов. XOR всех элементов даст a ^ b. Найдём любой бит, где они различаются: rightmostBit = (a^b) & -(a^b). Разделим элементы на две группы по этому биту — в каждой XOR даст один из уникальных. O(n) время, O(1) память.
Hamming Distance — количество различающихся битов? XOR двух чисел даёт 1 в позициях, где биты различаются. Считаем 1-биты в результате через Brian Kernighan: let xor = a ^ b; let count = 0; while (xor) { xor &= xor - 1; count++; }.
Зачем нужен n & -n (lowbit)? В two’s complement -n = ~n + 1. Пример: n=12 (1100), -n = 0100, n & -n = 0100. Выделяет rightmost 1-bit. Используется в Fenwick Tree для вычисления parent/child за O(1).

Сгенерировать все подмножества множества из n элементов?

for (let mask = 0; mask < (1 << n); mask++) {
  for (let i = 0; i < n; i++) {
    if (mask & (1 << i)) console.log(i);
  }
}

Время O(n · 2ⁿ).

Reverse Bits — развернуть биты числа.

let res = 0;
for (let i = 0; i < 32; i++) {
  res = (res << 1) | ((n >> i) & 1);
}
return res >>> 0; // unsigned

Время O(1) — фиксированные 32 итерации.

Почему в JS битовые операции только для 32 бит? JS Number — IEEE 754 double (53 бита мантиссы), но bitwise по спецификации приводит к int32 signed. Для больших чисел используй BigInt: 1n << 50n корректно работает.

Чеклист на собес

Знай 8 базовых трюков (set, clear, toggle, test bit; lowbit; popcount; power of 2).
Помни про signed/unsigned в JS — >>> 0 для unsigned интерпретации.
Аккуратно со скобками: (x & mask) === target, не x & mask === target.
При работе с большими числами — BigInt.
Для bitmask DP убедись, что n ≤ 20 (иначе TLE).