re:re:actable
Урок 094 минуты чтения

Что такое bit manipulation?

На этой странице
Кратко

Bit manipulation - работа с числами на уровне битов. На собеседованиях она нужна для XOR-задач, масок, множеств маленького размера, степеней двойки и перебора подмножеств.

Вопрос

Что такое bit manipulation и какие битовые операции нужно знать?

Биты простыми словами

Число можно представить в двоичной системе.

5 = 101

Это значит:

1 * 4 + 0 * 2 + 1 * 1 = 5

Основные операции

ОперацияJSПример
ANDa & bбит равен 1, если оба бита 1
OR`ab`
XORa ^ bбит равен 1, если биты разные
NOT~aинверсия битов
Left shifta << kумножение на 2^k
Right shifta >> kделение на 2^k с учетом знака
Unsigned right shifta >>> kсдвиг вправо без знака

Важный нюанс JavaScript

Большинство битовых операций в JS работают с 32-bit signed integers.

Это значит:

  • очень большие числа могут вести себя неожиданно;
  • для больших integer лучше BigInt;
  • для обычных interview-задач с небольшими числами это обычно нормально.

XOR

Свойства XOR:

a ^ a = 0
a ^ 0 = a
a ^ b = b ^ a

Классическая задача: одно число встречается один раз, остальные дважды.

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

Почему работает:

дубликаты уничтожают друг друга через a ^ a = 0

Проверить четность

function isOdd(num: number): boolean {
  return (num & 1) === 1
}

Последний бит:

  • 0 - число четное;
  • 1 - число нечетное.

Проверить степень двойки

function isPowerOfTwo(num: number): boolean {
  return num > 0 && (num & (num - 1)) === 0
}

Почему:

8  = 1000
7  = 0111
8 & 7 = 0000

У степени двойки ровно один установленный бит.

Установить, снять и проверить бит

Проверить бит:

function hasBit(mask: number, bit: number): boolean {
  return (mask & (1 << bit)) !== 0
}

Установить бит:

function setBit(mask: number, bit: number): number {
  return mask | (1 << bit)
}

Снять бит:

function clearBit(mask: number, bit: number): number {
  return mask & ~(1 << bit)
}

Переключить бит:

function toggleBit(mask: number, bit: number): number {
  return mask ^ (1 << bit)
}

Маска множества

Если элементов мало, например n <= 20, множество можно хранить числом.

mask = 0b101

Это значит:

элементы 0 и 2 включены

Перебор всех подмножеств:

function subsetsByMask(nums: number[]): number[][] {
  const result: number[][] = []
  const total = 1 << nums.length
 
  for (let mask = 0; mask < total; mask++) {
    const subset: number[] = []
 
    for (let bit = 0; bit < nums.length; bit++) {
      if ((mask & (1 << bit)) !== 0) {
        subset.push(nums[bit])
      }
    }
 
    result.push(subset)
  }
 
  return result
}

Сложность:

Time: O(n * 2^n)
Space: O(n) без учета output

Когда узнавать bit manipulation

Слова-подсказки:

  • bit;
  • mask;
  • subset;
  • XOR;
  • appears twice;
  • power of two;
  • set/unset/toggle;
  • permissions flags;
  • n <= 20.

Что важно помнить: частые ошибки

  • Забывать скобки: (mask & (1 << bit)) !== 0.
  • Путать & и &&, | и ||.
  • Использовать bit operations с большими числами в JS.
  • Не учитывать отрицательные числа.
  • Думать, что bit tricks всегда делают код лучше.
  • Применять mask, когда n слишком большое.

Что отвечать на собеседовании?

Bit manipulation работает с двоичным представлением чисел. Основные операции: AND, OR, XOR, NOT и shifts. XOR полезен для задач с парными дубликатами, num & (num - 1) - для проверки степени двойки, а bitmask позволяет хранить множество маленького размера и перебирать подмножества. В JavaScript нужно помнить про 32-bit signed поведение битовых операций.

Мини-шпаргалка

  • & - оба бита 1.
  • | - хотя бы один бит 1.
  • ^ - биты разные.
  • 1 << bit - маска бита.
  • mask & (1 << bit) - проверить бит.
  • mask | (1 << bit) - поставить бит.
  • mask & ~(1 << bit) - снять бит.
  • a ^ a = 0.
  • n & (n - 1) убирает младший установленный бит.

Документация

MDN: Bitwise operators, cp-algorithms: Bit manipulation.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам