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

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

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

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

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

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

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

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

Источники: Википедия: Битовая операция, MDN (англ.): Bitwise AND (&)

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; }

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

def find_unique(nums):
    acc = 0
    for n in nums:
        acc ^= n
    return acc

def set_bit(mask, i): return mask | (1 << i)
def clear_bit(mask, i): return mask & ~(1 << i)
def has_bit(mask, i): return (mask & (1 << i)) != 0

function findUnique(array $nums): int {
    $acc = 0;
    foreach ($nums as $n) $acc ^= $n;
    return $acc;
}
function setBit(int $mask, int $i): int { return $mask | (1 << $i); }
function clearBit(int $mask, int $i): int { return $mask & ~(1 << $i); }
function hasBit(int $mask, int $i): bool { return ($mask & (1 << $i)) !== 0; }

    public static int findUnique(int[] nums) {
        int acc = 0;
        for (int n : nums) acc ^= n;
        return acc;
    }

    public static int setBit(int mask, int i) { return mask | (1 << i); }

    public static int clearBit(int mask, int i) { return mask & ~(1 << i); }

    public static boolean hasBit(int mask, int i) { return (mask & (1 << i)) != 0; }

    public static int FindUnique(int[] nums) {
        int acc = 0;
        foreach (int n in nums) acc ^= n;
        return acc;
    }

    public static int SetBit(int mask, int i) { return mask | (1 << i); }

    public static int ClearBit(int mask, int i) { return mask & ~(1 << i); }

    public static bool HasBit(int mask, int 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», «установить, снять, переключить или проверить бит» или «упаковать много флагов да/нет в одно целое число». Решение на нём обычно укладывается в O(1)/O(n).

• •найти единственное или уникальное число через 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), то есть константа.