Битовые манипуляции

Битовые манипуляции: как это работает?

Число это ряд битов, каждый вдвое дороже соседа справа. Бит i стоит 2 в степени i.

Сдвиг влево на один удваивает число. Сдвиг вправо делит пополам и теряет последний бит.

AND с маской оставляет только те биты, что есть в маске. Так читают один бит.

OR ставит бит, а XOR его переключает. Бит, сложенный по XOR сам с собой, даёт ноль.

Этот факт и есть весь приём поиска одинокого значения. Каждая пара взаимно уничтожается.

n AND n минус один снимает младший установленный бит. Повторение этого считает установленные биты.

1. n = 1100Двенадцать в двоичной записи. У него два установленных бита.
2. n & 1 = 0Последний бит нулевой, значит число чётное.
3. n >> 2 = 11Два сдвига вправо оставляют тройку.
4. n & (n - 1) = 1000Вычитание единицы даёт 1011, и AND снимает младший установленный бит.
5. два круга дают нольЗначит у двенадцати ровно два установленных бита.

function findUnique(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
function setBit(mask, i) { return mask | (1 << i); }
function clearBit(mask, i) { return mask & ~(1 << i); }
function hasBit(mask, i) { return (mask & (1 << i)) !== 0; }

Битовые манипуляции: разбор примера

Посчитать биты у всех чисел подряд

Для каждого числа от 0 до n посчитайте, сколько у него установленных битов.

Считать каждое отдельно можно, но это повторяет кучу работы.

Снятие младшего установленного бита даёт меньшее число, уже посчитанное.

Значит ответ для i это ответ для i AND i минус один плюс единица.

function countBits(n) {
    const bits = new Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        // i & (i - 1) clears the lowest set bit, so it is always smaller
        bits[i] = bits[i & (i - 1)] + 1;
    }

    return bits;
}

Битовые манипуляции: когда применять?

Эти формулировки в условии ведут сюда:

• •найти единственное или уникальное число через XOR
• •установить, снять, переключить или проверить бит
• •упаковать много флагов да/нет в одно целое число
• •подсчёт установленных битов или проверка степени двойки

Битовые манипуляции: с чем путают?

• Хеш-множество / словарь (Hash set / map): Множество отвечает про принадлежность для любого ключа. Битовая маска умеет это для 32 известных элементов без памяти.
• Математика и теория чисел (НОД, решето, модульная арифметика) (Math and number theory (GCD, sieve, modular)): Оба работают с самим числом. Та страница про делители и простые, эта про биты.
• Бэктрекинг (Backtracking): Подмножества можно перечислить простым счётом от нуля. Бэктрекинг строит тот же список рекурсией.
• Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix)): Поразрядная сортировка читает разряды, иногда как биты. Её цель группировка, а не переключение.

Битовые манипуляции: частые ошибки

• Сдвигают дальше 31 бита

  Битовые операции JavaScript работают на 32 битах и заворачиваются. Дальше нужен BigInt.

• Забывают про знаковый бит

  Результат сдвига может вернуться отрицательным. Для простого подсчёта берите беззнаковый сдвиг.

• Путают AND и OR

  AND читает или снимает, а OR ставит. Их перестановка даёт молча неверную маску.

• Берут биты там, где важна ясность

  Массив булевых значений читается лучше и работает так же быстро. Маска нужна, когда ограничение это память.

Битовые манипуляции: задачи с собеседований

• Одинокое число: Каждая пара сама себя уничтожает под XOR.
• Число единичных битов: Снимайте младший установленный бит, пока не станет ноль.
• Подсчёт битов: Каждый ответ переиспользует уже посчитанный меньший.
• Пропущенное число: Сложите по XOR индексы со значениями.
• Подмножества: Считайте от нуля до двойки в степени n.
• Степень двойки: Верно ровно тогда, когда n AND n минус один равно нулю.
• Сумма двух целых: XOR даёт сумму, а сдвинутый AND даёт перенос.

Битовые манипуляции: сложность по времени и памяти

O(1)/O(n)

Одна операция стоит O(1) на 32-битном значении. Проход по битам это O(32), то есть константа.