Битовые трюки

Команда ls -l печатает права файла строкой вроде rwxr-xr--, а chmod принимает их числом 754. Это одно и то же: девять флажков «может ли владелец, группа или остальные читать, писать, запускать», записанные как девять бит числа. 7 — это 111, все три права, 5 — 101, чтение и запуск, 4 — 100, только чтение. Ниже — число из шестнадцати бит, которое можно переключать по одному, и приёмы, которые делают с ним что-то полезное одной операцией.

Выберите x & (x − 1) и посмотрите на столбик: вычитание единицы превращает младшую единицу числа в ноль, а нули под ней — в единицы; «и» с исходным числом стирает всё это вместе с той самой единицей. Остальные биты не меняются. Нажмите «Записать результат в x» несколько раз — единицы исчезают по одной справа налево, и счётчик дойдёт до нуля ровно за столько шагов, сколько в числе единиц.

Идея

Число из n бит — это подмножество набора из n элементов: бит i равен единице, если элемент i в подмножестве. Тогда операции над множествами — это операции над битами: объединение — «или» (a | b), пересечение — «и» (a & b), разность — «и» с отрицанием (a & ~b), принадлежность — проверка бита (a >> i & 1). Процессор делает каждую из них над 64 битами одной командой, без циклов и ветвлений.

Как числа хранятся в двоичном виде, что такое дополнительный код и почему −1 — это все единицы, рассказано в главе курса о битах. Здесь — приёмы, которые из этого следуют.

Приёмы

• x & (x − 1) стирает младшую единицу. Отсюда подсчёт единиц за столько шагов, сколько их в числе: стирать, пока не ноль. Приём описал Питер Вегнер в 1960 году, а широко известным он стал по задаче из книги Кернигана и Ритчи о языке C. И проверка «степень ли двойки»: у степени двойки единица одна, и после стирания остаётся ноль.
• x & −x оставляет только младшую единицу. В дополнительном коде −x = ~x + 1: все биты переворачиваются, и прибавленная единица пробегает переворот до младшей единицы x. Совпадает с x только этот бит. На этом шаге держится дерево Фенвика: от позиции i оно прыгает на i & −i.
• x | (x + 1) ставит младший ноль — зеркальный приём.
• Подсчёт единиц одной командой. В процессорах есть инструкция для этого (в x86 — POPCNT); в Go до неё доходит bits.OnesCount, в Python — int.bit_count() с версии 3.10. Задача о счётчике туда-обратно держится на ней: число переключившихся бит между a и b — это число единиц в a XOR b.
• Сдвиги — умножение и деление на степени двойки, а перемешивание бит двух координат даёт Z-порядок из статьи о кривых, заполняющих плоскость.
• Код Грея x ^ (x >> 1) нумерует числа так, что соседние отличаются ровно одним битом. Фрэнк Грей из Bell Labs запатентовал его для передачи сигнала импульсами, а сегодня им же нумеруют положения датчиков угла: на стыке двух положений датчик не выдаст случайное третье.

Маски встречаются далеко за пределами олимпиад. Права Unix — девять бит, и chmod g+w — это «или» с маской 0o020. Маска подсети /24 — это 24 единицы, 255.255.255.0, и адрес сети — адрес & маска. Шахматные программы хранят позицию «битовыми досками»: по 64-битному числу на каждый вид фигур, и все ходы коня со всех полей сразу считаются сдвигами и масками. Большой сборник таких приёмов — книга Генри Уоррена «Алгоритмические трюки для программистов».

Перебор подмножеств

Раз подмножество — это число, перебрать все подмножества набора из n элементов — значит пройти числа от 0 до 2ⁿ − 1. Без рекурсии и без списков. Возьмём 16 вещей из статьи о рюкзаке и переберём все 65 536 наборов. Вес набора не нужно складывать заново: набор — это тот же набор без младшей вещи плюс она сама, и вес[маска] = вес[маска ^ младшая] + вес вещи — одно сложение на набор.

Два родственных приёма. Перебрать только наборы ровно из k вещей помогает приём Госпера — формула, которая по числу с k единицами даёт следующее по величине с тем же числом единиц; Билл Госпер записал её в сборнике HAKMEM в 1972 году. А перебрать все подмножества данной маски m позволяет цикл s = (s − 1) & m: вычитание единицы с последующим «и» даёт следующую подмаску по убыванию.

Это важно для динамики по маскам: перебор подмасок всех масок для 20 элементов — 3,5 миллиарда шагов, а не 2⁴⁰, то есть триллион.

Код

Права доступа, подсчёт единиц и младший бит, полный перебор наборов для похода, приём Госпера и проверка формулы 3ⁿ:

Полный перебор находит те же 64 балла, что таблица динамики в статье о рюкзаке, — и подтверждает её ответ, не доверяя рекурсии. 65 536 наборов — это пустяк; 40 вещей дали бы уже триллион, и тут нужна таблица или встреча посередине, которая перебирает две половины по 2²⁰.

Сколько это стоит

Операция над словом — одна команда процессора, поэтому множества из 64 элементов складываются, пересекаются и проверяются за O(1). Для больших множеств — битовые массивы: n бит в n/64 словах, и операции над целым множеством стоят O(n/64), в 64 раза дешевле, чем по элементу. Перебор подмножеств — 2ⁿ, подмасок всех масок — 3ⁿ, и на практике это предел примерно в 25 и 16 элементов соответственно.

Цена — читаемость. x & -x в коде без комментария не узнает никто, кроме тех, кто уже знает. Поэтому битовые приёмы прячут в функции с понятными именами — как bits.OnesCount и int.bit_count — и пишут рядом, что они делают.

Задачи

Задача — chmod: права доступа меняются восьмеричными числами и символьными командами вроде go-w или u=rwx,g=rx,o=, и каждая команда — одна-две битовые операции с масками.