Что такое bit manipulation?
На этой странице
Bit manipulation - работа с числами на уровне битов. На собеседованиях она нужна для XOR-задач, масок, множеств маленького размера, степеней двойки и перебора подмножеств.
Вопрос
Что такое bit manipulation и какие битовые операции нужно знать?
Биты простыми словами
Число можно представить в двоичной системе.
5 = 101Это значит:
1 * 4 + 0 * 2 + 1 * 1 = 5Основные операции
| Операция | JS | Пример |
|---|---|---|
| AND | a & b | бит равен 1, если оба бита 1 |
| OR | `a | b` |
| XOR | a ^ b | бит равен 1, если биты разные |
| NOT | ~a | инверсия битов |
| Left shift | a << k | умножение на 2^k |
| Right shift | a >> k | деление на 2^k с учетом знака |
| Unsigned right shift | a >>> 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)убирает младший установленный бит.