Bitwise Operations (Битовые операции)

Битовые операции работают напрямую с двоичным представлением чисел. В JavaScript операнды приводятся к 32-битным знаковым целым (кроме BigInt), результат — тоже 32-битное целое.

Операторы

Оператор	Название	Пример	Результат
&	AND (И)	5 & 3 → 0101 & 0011	1 (0001)
|	OR (ИЛИ)	5 | 3 → 0101 | 0011	7 (0111)
^	XOR (исключающее ИЛИ)	5 ^ 3 → 0101 ^ 0011	6 (0110)
~	NOT (инверсия)	~5	-6 (инвертирует все биты)
<<	сдвиг влево	5 << 1	10
>>	сдвиг вправо (знаковый)	5 >> 1	2
>>>	сдвиг вправо (беззнаковый)	-1 >>> 0	4294967295

Сдвиги = умножение и деление на степени двойки

Сдвиг битов влево/вправо эквивалентен умножению/делению на 2^j:

n << j  ===  n * 2**j    // сдвиг влево: 3 << 2 = 3 * 4 = 12
n >> j  ===  Math.floor(n / 2**j) // сдвиг вправо: 12 >> 2 = 3
1 << j  ===  2**j         // быстрая степень двойки: 1 << 4 = 16

Сдвиг быстрее арифметического умножения/деления и часто используется в низкоуровневом коде и битовых масках.

Как работает XOR

XOR даёт 1, только если биты различаются. Полезные свойства:

a ^ a === 0        // число, XOR-нутое само с собой, = 0
a ^ 0 === a        // XOR с нулём не меняет число
a ^ b ^ a === b    // XOR обратим — двойное применение возвращает исходное

Отсюда классический приём — найти одинокий элемент (все остальные встречаются парами):

// LeetCode 136. Single Number — O(n) время, O(1) память
function singleNumber(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
// [4,1,2,1,2] → 4  (парные взаимно уничтожаются)

Типовые битовые приёмы

// Проверить чётность (последний бит)
n & 1            // 1 — нечётное, 0 — чётное
 
// Проверить, установлен ли i-й бит
(n >> i) & 1      // 1 если бит установлен
 
// Установить i-й бит
n | (1 << i)
 
// Снять i-й бит
n & ~(1 << i)
 
// Переключить (toggle) i-й бит
n ^ (1 << i)
 
// Убрать самый младший установленный бит
n & (n - 1)      // используется для подсчёта единичных битов
 
// Проверить, что число — степень двойки
n > 0 && (n & (n - 1)) === 0

Подсчёт единичных битов (Brian Kernighan)

// Считаем количество установленных битов за O(число единиц)
function countBits(n) {
    let count = 0;
    while (n) {
        n &= n - 1; // убираем самый младший установленный бит
        count++;
    }
    return count;
}

Битовые маски

Набор булевых флагов можно хранить в одном числе — каждый бит отвечает за отдельный флаг. Компактно и быстро.

const READ = 1 << 0;   // 001
const WRITE = 1 << 1;  // 010
const EXEC = 1 << 2;   // 100
 
let perms = READ | WRITE;   // 011 — есть чтение и запись
const canWrite = (perms & WRITE) !== 0; // true
perms &= ~WRITE;            // снять флаг записи

⚠️ В JS битовые операции работают только с 32-битными целыми: 1 << 31 уже уходит в отрицательные, а для больших чисел нужен BigInt (1n << 40n).

См. также

• o-1-constant — битовые операции за O(1)