Паттерн: Битовые операции

Признак в условии

• «за O(1) памяти», хотя напрашивается множество
• числа встречаются парами, кроме одного
• степень двойки, счёт единичных битов, флаги и маски
• нужно закодировать набор булевых признаков компактно

Приёмы, которые надо знать наизусть

выражение	что делает
a ^ a === 0, a ^ 0 === a	XOR уничтожает пары
n & (n - 1)	снимает младший установленный бит
n & -n	оставляет только младший установленный бит
n >> 1	делит на два, убирая младший бит
n & 1	младший бит: чётность
mask & flag	проверка флага в маске
mask | flag	установка флага
mask & ~flag	снятие флага

Шаблон

// единственное непарное число
return nums.reduce((acc, n) => acc ^ n, 0);

// степень двойки
return n > 0 && (n & (n - 1)) === 0;

// число единичных битов для всех i до n: динамика
out[i] = out[i >> 1] + (i & 1);

Сложность

O(1) на операцию, O(n) на проход. Память O(1) - в этом весь смысл.

Осторожно в JS

Побитовые операторы приводят число к 32-битному знаковому целому. Для значений больше 2³¹−1 результат будет неожиданным; сдвиг >>> даёт беззнаковый. Для больших чисел - BigInt, но битовые трюки с ним медленнее.

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

• забыта проверка на положительность: для нуля n & (n - 1) тоже даёт ноль
• путают >> и >>> на отрицательных числах
• сравнивают mask & flag с единицей вместо самого flag - ломается на многобитных флагах

Мнемоника

«XOR съедает пары, минус один снимает младший бит»

Не путать с

• Хеш-таблица - битовая маска заменяет множество, когда элементов до 32–64 и они плотные
• Динамическое программирование - динамика по подмножествам - это динамика, у которой состояние хранится маской

Задачи на этот паттерн

• единственное непарное число
• число единичных битов
• степень двойки

Суть

Число в памяти это набор битов. Побитовые операции дают O(1)-трюки: проверку чётности, степени двойки, поиск непарного элемента, компактное хранение множеств маской.

Операторы в JS

Оператор	Что делает	Пример
&	И	6 & 3 → 2
|	ИЛИ	6 | 3 → 7
^	исключающее ИЛИ	6 ^ 3 → 5
~	НЕ	~5 → -6
<<	сдвиг влево	1 << 4 → 16
>>	сдвиг вправо со знаком	-8 >> 1 → -4
>>>	сдвиг вправо с нулями	-8 >>> 1 → 2147483644

Важно: операнды приводятся к 32-битному целому со знаком. 2 ** 32 | 0 это 0, 2 ** 31 | 0 это -2147483648. Для больших чисел есть BigInt (1n << 40n), но смешивать с Number нельзя.

Как распознать по условию

• «каждый элемент встречается дважды, кроме одного» → XOR;
• «без дополнительной памяти», «без сложения / умножения»;
• «степень двойки», «посчитай единичные биты»;
• n до 20 и нужны все подмножества → маски;
• состояние из нескольких флагов (DP по маскам).

Шаблоны

const bit = (x, i) => (x >> i) & 1;      // проверить
const set = (x, i) => x | (1 << i);      // установить
const clear = (x, i) => x & ~(1 << i);   // сбросить
const flip = (x, i) => x ^ (1 << i);     // переключить
const lowest = (x) => x & -x;            // младший единичный бит

function single(nums) {                  // непарный элемент
  return nums.reduce((acc, x) => acc ^ x, 0);
}

function popcount(n) {                   // число единиц
  let c = 0;
  while (n) { n &= n - 1; c++; }
  return c;
}

for (let mask = 0; mask < 1 << n; mask++) { // все подмножества
  const subset = [];
  for (let i = 0; i < n; i++) if ((mask >> i) & 1) subset.push(arr[i]);
}

Приоритет операторов

=== связывает сильнее, чем &: n & (n - 1) === 0 читается как n & ((n - 1) === 0). Всегда ставь скобки: (n & (n - 1)) === 0.

Сложность

Одна операция O(1). Перебор масок O(n · 2ⁿ). Popcount по Кернигану O(число единиц).

Ловушки

• Забыть, что числа 32-битные: переполнение молча.
• Скобки и приоритет & против ===.
• Считать, что ~x это -x: на самом деле ~x === -x - 1.
• x.toString(2) для отрицательного даёт -101, а не дополнительный код: нужно (x >>> 0).toString(2).

Что спросят на собесе

• Найди число без пары за O(1) памяти.
• Как проверить степень двойки?
• Чем >> отличается от >>>?
• Почему 2 ** 32 | 0 равно 0?