Алгоритмы с нуля ALG · 12 · 01

Битовые манипуляции: маски, сдвиги и трюк n & (n-1)

Шесть побитовых операторов плюс однобитная маска дают O(1)-идиомы проверить, установить, сбросить и переключить бит. Степень двойки это n & (n-1) == 0; popcount это цикл Кернигана n &= n-1, O(единичных битов). В JS побитовые 32-битные знаковые, для беззнакового нужен >>>.

ALG ◷ 24 min

Поле прав хранит восемь флагов: can-read, can-write, can-delete и ещё пять. Можно хранить восемь булевых значений, массив или множество. А можно хранить один байт и сделать каждый бит одним флагом. Теперь «есть ли у пользователя право записи?» — это одна машинная инструкция, «выдать запись» — ещё одна, и весь набор прав помещается в регистр, который процессор сравнивает за один такт. Это не микрооптимизация из ушедшей эпохи — именно так устроены права файлов в Unix, заголовки сетевых протоколов, шахматные движки, фильтры Блума и битовые карты колонок в базах данных. Под каждым целым числом лежит ряд битов, и горстка операторов позволяет читать и переписывать эти биты напрямую. Этот урок — набор инструментов: шесть побитовых операторов, идиомы масок, построенные из них, и две классики — проверка степени двойки и подсчёт единичных битов — которые показывают идиомы в действии.

Цель

После этого урока ты можешь назвать шесть побитовых операторов и сказать, что именно делает каждый бит за битом: AND (&) сохраняет бит только там, где он есть у обоих входов, OR (|) — где есть хотя бы у одного, XOR (^) — где они различаются, NOT (~) переворачивает каждый бит, а два сдвига (<<, >>) двигают битовый узор влево или вправо. Ты можешь построить четыре идиомы масок из этих операторов — проверить бит i через (x >> i) & 1, установить через x | (1 << i), сбросить через x & ~(1 << i), переключить через x ^ (1 << i) — и объяснить, почему единственная сдвинутая 1 (one-hot маска) это общий ингредиент. Ты можешь написать проверку степени двойки n > 0 && (n & (n - 1)) === 0 и объяснить, почему вычитание единицы и AND стирают младший установленный бит. Ты можешь реализовать подсчёт единичных битов Брайана Кернигана (вес Хэмминга) и назвать его стоимость: O(числа установленных битов), а не O(размера слова). И ты знаешь одну ловушку JavaScript, которая кусает всех: побитовые операторы приводят операнды к 32-битным знаковым целым, поэтому 1 << 31 отрицателен, и ты берёшь >>> (или >>> 0), когда хочешь беззнаковый 32-битный результат.

Идея

Каждое целое — это ряд битов

Число 13 внутри машины это не «тринадцать» — это битовый узор 1101 (8 + 4 + 0 + 1). Битовые манипуляции означают работу с этими отдельными битами напрямую, а не с десятичным значением числа. Операторы, которые это делают, называются побитовыми, и их ровно шесть, которые стоит запомнить.

Шесть операторов

Прежде чем строить что-то полезное, нужно точно знать, что каждый оператор делает с битами — потому что путаница AND с OR там, где нужен OR, это самый частый источник трудноуловимых ошибок в флаговой логике. Каждый оператор ниже действует на каждую битовую позицию независимо — бит i результата зависит только от бита i входов.

AND (&) — бит результата равен 1, только если оба входных бита равны 1. Используется чтобы читать или сбрасывать биты: 1100 & 1010 = 1000.
OR (|) — бит результата равен 1, если хотя бы один входной бит равен 1. Используется чтобы устанавливать биты: 1100 | 1010 = 1110.
XOR (^) — бит результата равен 1, только если входные биты различаются. Используется чтобы переключать биты и находить различия: 1100 ^ 1010 = 0110. XOR обратен сам себе: x ^ y ^ y === x.
NOT (~) — переворачивает каждый бит (унарный). ~1100 переворачивает все биты, включая старшие, которые обычно не видны.
Сдвиг влево (<<) — двигает биты влево, заполняя нулями справа. 1 << 3 = 1000 (десятичное 8). Каждый сдвиг влево на один умножает на два.
Сдвиг вправо (>>) — двигает биты вправо. 1101 >> 1 = 110 (десятичное 6). Каждый сдвиг вправо на один делит на два (в сторону минус бесконечности, потому что в большинстве языков >> копирует знаковый бит).

В итоге: AND и OR отвечают за чтение и запись, XOR — за переключение и сравнение, NOT — за инверсию, сдвиги — за масштабирование. Когда встретишь незнакомую битовую идиому, один из этих шести всегда окажется в её основе.

One-hot маска: ключевой строительный блок

Почти каждый битовый трюк начинается с маски — числа, чьи биты выбирают позиции, которые тебе важны. Самая полезная маска это единственная 1, сдвинутая в позицию i: 1 << i. Это даёт «one-hot» узор ровно с одним установленным битом, в позиции i. Скомбинируй её с оператором — и получишь четыре идиомы, которые делают почти всё:

проверить бит i:  (x >> i) & 1     ->  0 или 1
установить бит i: x | (1 << i)     ->  делает бит i равным 1
сбросить бит i:   x & ~(1 << i)    ->  делает бит i равным 0
переключить бит i: x ^ (1 << i)    ->  переворачивает бит i

Чтобы установить бит, делай OR с маской, где этот бит включён. Чтобы сбросить бит, делай AND с маской, где этот бит выключен (~(1 << i) это все единицы, кроме позиции i). Чтобы переключить — XOR с one-hot маской. Чтобы проверить — сдвинь нужный бит вниз в позицию 0 и отсеки остальное через & 1. Четыре оператора, одна маска, любая однобитная операция.

Классика 1: является ли n степенью двойки?

Когда встретишь проверку размера или выравнивания в аллокаторе памяти или при ресайзе хэш-таблицы, этот трюк почти наверняка прячется внутри. У степени двойки ровно один установленный бит: 1, 10, 100, 1000, ... (десятичные 1, 2, 4, 8). Вот трюк, который проверяет это за O(1) без цикла:

n & (n - 1) === 0      (для n > 0)

Почему это работает? Вычитание 1 из числа переворачивает его младший установленный бит в 0 и превращает все биты ниже него в 1. Так что 1000 - 1 = 0111. AND этих двух — 1000 & 0111 — не имеет общих битов, давая 0. Если у n было больше одного установленного бита, старшие биты переживают AND, и результат ненулевой. Защита n > 0 важна: 0 & (0 - 1) тоже равно 0, но 0 не степень двойки.

Классика 2: подсчёт единичных битов (вес Хэмминга)

Вес Хэмминга числа это сколько его битов равны 1. Наивный способ проверяет все 32 позиции. Алгоритм Брайана Кернигана умнее: n &= n - 1 сбрасывает младший установленный бит (то же наблюдение про n - 1, что и выше), так что ты делаешь итерацию один раз на установленный бит и останавливаешься в момент, когда n доходит до нуля:

count = 0
while n != 0:
    n &= n - 1      // стереть младший установленный бит
    count += 1

Число с тремя установленными битами стоит три итерации, а не тридцать две. Это делает цикл O(числа установленных битов) — дешевле, чем сканировать каждую позицию, когда число разреженное.

Подсчёт Брайана Кернигана на n = 13 (1101). Каждый шаг делает n &= n - 1, что стирает единственный младший установленный бит (выделен). Три установленных бита означают три итерации, затем n доходит до 0 и цикл останавливается — стоимость это число единичных битов, а не размер 32-битного слова.

Код

Подсчёт единичных битов Брайана Кернигана

Весь алгоритм это один цикл. Трюк на строке, которая сбрасывает младший установленный бит; всё остальное — учёт.

1 function popcount(x) {

2 x = x >>> 0; // treat the 32 bits as unsigned

3 let count = 0;

4 while (x !== 0) {

5 x &= x - 1; // clear the lowest set bit

6 count++;

7 }

8 return count;

9 }

L2 В JS побитовые операторы работают над 32-битными ЗНАКОВЫМИ целыми. Беззнаковый сдвиг вправо >>> 0 переинтерпретирует биты как беззнаковое 32-битное значение, поэтому число с установленным битом 31 считается правильно, а не зацикливается на отрицательном.
L4 Цикл, пока остаются установленные биты. Разреженное число (мало единиц) выходит быстро; именно это делает его O(установленных битов), а не O(32).
L5 Суть: x - 1 переворачивает младший установленный бит в 0 и превращает все биты ниже него в 1; AND с x стирает ровно этот один бит и оставляет остальное нетронутым.

Запусти: маски, степень двойки и popcount (подсчёт единичных битов) вместе

Одна и та же one-hot маска 1 << i приводит в действие каждую однобитную идиому ниже. Смотри на четыре операции масок над x = 1010, затем две классики.

Вывод

Бит 1 числа 1010 равен 1. Установка бита 0 даёт 1011; сброс бита 3 даёт 10; переключение бита 2 даёт 1110. 16 это 10000 (один установленный бит), поэтому степень двойки; 24 это 11000 (два бита), поэтому нет. 13 это 1101 (три установленных бита), а 255 это 11111111 (восемь). Ничто здесь не зацикливается по десятичным значениям — каждая строка это пара битовых операций.

Пошаговый разбор

Пройдём popcount Брайана Кернигана на n = 13 (1101), наблюдая, как n &= n - 1 стирает один установленный бит за шаг, пока n не дойдёт до нуля.

1 x = 13 (1101), count = 0

2 x != 0 -> x &= x - 1; count++

3 x != 0 -> x &= x - 1; count++

4 x != 0 -> x &= x - 1; count++

5 x == 0 -> stop

6 return count

Сложность

Одиночные операции: O(1) на машинном слове

Каждый из шести побитовых операторов и каждая идиома маски (проверить, установить, сбросить, переключить) это одна инструкция процессора над значением, помещающимся в регистр. Для целых фиксированной ширины (32 или 64 бита) это O(1) по времени и O(1) по памяти — без циклов, без аллокаций. Проверка степени двойки n & (n - 1) === 0 это две операции и сравнение: тоже O(1).

Подсчёт битов: O(установленных битов) с Брайаном Керниганом

Подсчёт установленных битов это единственное место, где появляется цикл, и два подхода различаются:

                              итераций              время
наивный (проверять позиции)   по одной на ширину    O(w)   (w = 32 или 64)
Брайан Керниган (n &= n-1)     по одной на УСТ. бит  O(popcount(n)) <= O(w)

Цикл Брайана Кернигана выполняется один раз на 1-бит, поэтому разреженное число (скажем, один установленный бит) стоит одну итерацию, тогда как наивное сканирование всегда стоит w. В худшем случае — все биты установлены — оба O(w), но Керниган никогда не хуже и обычно лучше.

Оговорка про «O(1)»: размер слова это константа, только если он фиксирован

Называть битовые операции «O(1)» предполагает, что целое помещается в одно машинное слово. Это верно для 32-битных и 64-битных целых. В момент, когда ты работаешь с целыми произвольной точности (JavaScript BigInt, Python int, библиотеки длинной арифметики), значение охватывает много слов, и побитовая операция над b-битным числом это O(b / размер слова) = O(b) — линейно по числу битов, а не константа. Так что «битовые трюки бесплатны» верно для целых фиксированной ширины и неверно для длинных целых.

Заметка про железо

У большинства процессоров есть выделенная инструкция POPCNT (population count — аппаратный подсчёт единичных битов), которая считает установленные биты за настоящее O(1), и компиляторы дают к ней доступ (C++ std::popcount, GCC __builtin_popcount). Алгоритм Брайана Кернигана это переносимый запасной вариант, когда такой инструкции (или интринсика) нет — например, в чистом JavaScript.

Практика 0 / 7

Какой оператор и маска УСТАНАВЛИВАЮТ бит i числа x в 1 (оставляя остальные биты без изменений)?

Что делает x & ~(1 << i)?

Почему n & (n - 1) === 0 (при n > 0) проверяет степень двойки?

popcount Брайана Кернигана выполняет n &= n - 1 в цикле. Сколько итераций он делает для n = 13 (двоичное 1101)?

В JavaScript, почему popcount начинается с x = x >>> 0?

Каково десятичное значение 1 << 5 ?

Сколько установленных битов (вес Хэмминга) у десятичного числа 255?

▸Почему это работает

Зачем вообще хранить данные в битах? Три причины держат битовые манипуляции в ежедневном использовании. (1) Память: набор до 64 булевых флагов помещается в одно 64-битное целое вместо 64 отдельных булевых — битовые маски, битсеты и фильтры Блума используют это. (2) Скорость: проверка или комбинирование целых наборов флагов это одна инструкция; шахматный движок представляет доску как 64-битные «битборды» и вычисляет все ходы коня парой сдвигов и OR. (3) Протоколы и форматы: права файлов Unix, заголовки IPv4, чанки PNG и битовые карты колонок базы пакуют поля в фиксированные битовые диапазоны, поэтому их чтение требует масок и сдвигов. Знание идиом это разница между обращением с ними как с непрозрачными магическими числами и прямым манипулированием ими.

▸Частая ошибка

Ловушка XOR-обмена. Два целых можно обменять без временной переменной через XOR: a ^= b; b ^= a; a ^= b;. Это забавный трюк для вечеринки, но у него есть фатальный краевой случай — если a и b это одна и та же переменная или указывают на одну память (swap(arr[i], arr[j]) при i === j), первый a ^= b устанавливает это место в 0, и значение уничтожено. У обычного обмена через временную переменную такой опасности нет, и современные компиляторы делают его настолько же быстрым. Используй XOR-обмен, чтобы понять XOR; не выкатывай его в продакшен.

▸Граничные случаи

Две защиты, которые все забывают. Первое, проверке степени двойки нужна защита n > 0: 0 & (0 - 1) равно 0, поэтому без неё 0 отчитывается как степень двойки (он ею не является). Второе, в JavaScript n & (n - 1) работает только в пределах 32 битов, потому что операнды приводятся к 32-битным знаковым целым — для значения выше 2^31 нужен BigInt и битовые операции длинной арифметики. Чистая алгебра битовых трюков всегда предполагает известную фиксированную ширину битов; перешагни эту границу — и целочисленная модель языка берёт верх.

▸Ещё практика

Шпаргалка по одному биту. Держи эти четыре в мышечной памяти; one-hot маска 1 << i это общий ингредиент. Проверить: (x >> i) & 1. Установить: x | (1 << i). Сбросить: x & ~(1 << i). Переключить: x ^ (1 << i). И две числовые классики: степень двойки это n > 0 && (n & (n - 1)) === 0; выделение младшего установленного бита это x & -x (удобно для перебора установленных битов). Почти любой вопрос про «биты» на собеседовании это одна из этих идиом в маскировке.

Проверь себя

Викторина

Объясни четыре однобитные идиомы масок и операторы за ними, проверку степени двойки и почему она работает, подсчёт битов Брайана Кернигана и его сложность, и оговорку про 32-битные знаковые в JavaScript.

Итог

Битовые манипуляции работают над отдельными битами числа, используя шесть операторов: AND & (бит установлен, если у обоих), OR | (бит установлен, если хотя бы у одного), XOR ^ (бит установлен, если различаются), NOT ~ (перевернуть все), и сдвиги << (×2) и >> (÷2).

One-hot маска 1 << i строит четыре однобитные идиомы:

Проверить бит i: (x >> i) & 1
Установить бит i: x | (1 << i)
Сбросить бит i: x & ~(1 << i)
Переключить бит i: x ^ (1 << i)

Две классики:

Степень двойки: n > 0 && (n & (n - 1)) === 0 — потому что n - 1 стирает младший установленный бит, а у степени двойки только этот один бит.
Подсчёт единичных битов (вес Хэмминга): цикл Брайана Кернигана n &= n - 1 выполняется один раз на установленный бит — O(установленных битов), а не O(размера слова).

Сложность: одиночные операторы и идиомы масок это O(1) на машинном слове фиксированной ширины; только длинные целые делают их O(битов).

Оговорка JavaScript: побитовые операторы приводят операнды к 32-битным знаковым целым, поэтому 1 << 31 отрицателен — берись за >>> (или >>> 0), когда хочешь беззнаковый 32-битный результат.

Теперь, когда встретишь проверку флага, ограничение по размеру или цикл подсчёта битов на ревью, ты назовёшь оператор в его основе, проверишь маску и поймаешь пропущенную защиту n > 0 до того, как она попадёт в продакшен.

Практика

Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.

вспомнитьприменитьуглубить0 из 5 завершено

Что-то непонятно?

Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.