Битовые операции: трюки, которые спрашивают на собеседованиях

Зачем это знать

Битовые операции редко нужны в прикладном коде — и именно поэтому их спрашивают. Задача на биты проверяет, понимаете ли вы, как число устроено внутри, или работаете с ним как с чёрным ящиком.

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

Пять операций, которые нужно знать

Числа в памяти хранятся в двоичном виде. Операции работают с каждым битом независимо.

AND (&) — бит остаётся, если он есть в обоих

  1100  (12)
& 1010  (10)
  ----
  1000  (8)

Главное применение — проверить или обнулить биты. n & 1 проверяет чётность: если младший бит единица, число нечётное.

6 & 1;  // 0 → чётное
7 & 1;  // 1 → нечётное

OR (|) — бит остаётся, если он есть хотя бы в одном

  1100  (12)
| 1010  (10)
  ----
  1110  (14)

Применяется, чтобы установить биты, не трогая остальные.

XOR (^) — бит остаётся, если он есть ровно в одном

  1100  (12)
^ 1010  (10)
  ----
  0110  (6)

XOR — самая полезная операция в задачах. У неё три свойства, из которых растёт половина трюков:

x ^ x === 0;      // число, сложенное само с собой, обнуляется
x ^ 0 === x;      // ноль ничего не меняет
// операция коммутативна и ассоциативна:
// a ^ b ^ a  ===  a ^ a ^ b  ===  0 ^ b  ===  b

Последняя строка и есть весь секрет: парные элементы взаимно уничтожаются, независимо от порядка.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Сдвиги (<<, >>)

Сдвиг влево на k — умножение на 2ᵏ, сдвиг вправо — целочисленное деление.

5 << 1;   // 10  (101 → 1010)
5 << 3;   // 40
20 >> 2;  // 5

Отдельно существует >>> — беззнаковый сдвиг вправо, который не сохраняет знаковый бит. Для отрицательных чисел >> и >>> дают разный результат, и это регулярно всплывает в багах.

NOT (~) — инверсия всех битов

~5;  // -6

Неочевидно, но объяснимо: в дополнительном коде ~x === -x - 1. Отсюда популярная идиома ~index для проверки indexOf: ~(-1) даёт 0 (ложь), а любой валидный индекс даёт ненулевое значение.

Трюк первый: найти единственное непарное число

Классика. В массиве все числа встречаются дважды, кроме одного. Найти его.

Очевидное решение — хеш-таблица со счётчиками, O(n) времени и O(n) памяти. Но условие часто требует O(1) памяти.

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

singleNumber([4, 1, 2, 1, 2]); // 4

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

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

Тот же приём решает задачу «найти пропущенное число в диапазоне 0..n»: сложим по XOR все индексы и все значения, парные сократятся.

function missingNumber(nums) {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }
  return result;
}

missingNumber([3, 0, 1]); // 2

Трюк второй: подсчёт единичных битов

Сколько единиц в двоичной записи числа? Наивно — проверять биты по одному, 32 итерации всегда.

Есть изящнее — алгоритм Брайана Кернигана:

function countBits(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // убирает самую правую единицу
    count++;
  }
  return count;
}

countBits(12); // 2  (1100)

Ключ в выражении n & (n - 1). Вычитание единицы превращает самый правый единичный бит в ноль, а все нули справа от него — в единицы. AND с исходным числом гасит этот бит и оставляет остальное:

n     = 1100
n - 1 = 1011
n & (n-1) = 1000   ← убрали одну единицу

Число итераций равно количеству единиц, а не 32. Для разреженных чисел это заметно быстрее.

Из этого же выражения растёт проверка на степень двойки:

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

isPowerOfTwo(16); // true
isPowerOfTwo(18); // false

У степени двойки ровно один единичный бит, поэтому после сброса остаётся ноль. Проверка n > 0 обязательна: для нуля и отрицательных выражение тоже даст ноль, но ответ должен быть false.

Трюк третий: перебор всех подмножеств

Если нужно перебрать все подмножества набора из n элементов, битовая маска — самый компактный способ. Каждое число от 0 до 2ⁿ − 1 кодирует подмножество: единичный бит на позиции i означает «элемент i включён».

function allSubsets(items) {
  const total = 1 << items.length; // 2^n
  const result = [];

  for (let mask = 0; mask < total; mask++) {
    const subset = [];

    for (let i = 0; i < items.length; i++) {
      if (mask & (1 << i)) {
        subset.push(items[i]);
      }
    }

    result.push(subset);
  }

  return result;
}

allSubsets(['a', 'b']);
// [[], ['a'], ['b'], ['a', 'b']]

Проверка mask & (1 << i) читается как «включён ли i-й бит». Это стандартная идиома, её стоит просто запомнить.

Сложность — O(2ⁿ · n). Подход работает примерно до n = 20, дальше количество подмножеств становится неподъёмным.

Полезные однострочники

// установить i-й бит
n | (1 << i)

// сбросить i-й бит
n & ~(1 << i)

// переключить i-й бит
n ^ (1 << i)

// проверить i-й бит
(n >> i) & 1

// оставить только самый правый единичный бит
n & -n

// поменять знак у числа
~n + 1

Выражение n & -n встречается в дереве Фенвика и заслуживает отдельного внимания: -n в дополнительном коде — это ~n + 1, и AND с исходным числом оставляет ровно младший единичный бит.

Подводные камни JavaScript

Здесь легко потерять часы отладки.

Битовые операции работают только с 32-битными целыми. Числа в JavaScript — 64-битные с плавающей точкой, но перед побитовой операцией движок приводит их к int32. Для чисел больше 2³¹ − 1 результат будет неожиданным:

2 ** 31;              // 2147483648
(2 ** 31) | 0;        // -2147483648  ← переполнение

Если нужны большие числа, используйте BigInt — он поддерживает побитовые операции без ограничения разрядности.

Сдвиг влево может дать отрицательное число.

1 << 31;   // -2147483648
1 << 32;   // 1  ← счётчик сдвига берётся по модулю 32

>> и >>> ведут себя по-разному для отрицательных.

-8 >> 1;   // -4   знак сохраняется
-8 >>> 1;  // 2147483644

В Python таких проблем нет: целые числа произвольной точности, но и >>> там отсутствует, а отрицательные числа ведут себя как бесконечная последовательность единиц слева.

Когда битовые трюки уместны

Честный ответ: реже, чем кажется. В прикладном коде читаемость почти всегда важнее микрооптимизации, и n % 2 === 0 понятнее, чем (n & 1) === 0. Современные компиляторы такие вещи оптимизируют сами.

Битовые операции оправданы, когда:

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

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

Что запомнить

• XOR уничтожает парные элементы — на этом строится большинство задач.
• n & (n - 1) сбрасывает самый правый единичный бит, отсюда счёт битов и проверка степени двойки.
• n & -n оставляет только младший единичный бит.
• Битовая маска компактно кодирует подмножества, работает до n ≈ 20.
• В JavaScript побитовые операции ограничены 32 битами — за пределами нужен BigInt.

Закрепите на практике

Начните с задачи на поиск дубликатов в массиве. Классическое решение через множество там очевидно, а вот вариант с ограничением по памяти заставит вспомнить именно про XOR.