Младшая единица: x & (x − 1), x & −x и их семейство

Если ты объяснишь, почему x & -x оставляет одну единицу, перечислишь номера единичных битов числа за число кругов, равное числу единиц, и скажешь, что делает x | (x + 1), - листай до «Теперь сам».

Как думаешь, сколько кругов нужно, чтобы найти три единицы

В числе 52 бита, из них единичных три: биты 3, 17 и 44. Нужен список их номеров. Программа проверяет биты по очереди, с нулевого по пятьдесят первый.

Прежде чем читать дальше, ответь себе: можно ли обойтись тремя кругами, не зная заранее, где стоят единицы? Можно. Замер - 15 шагов против 109. Для этого надо уметь за одно действие вытащить из числа его младшую единицу.

На что это похоже

Спидометр со счётчиком пробега показывает 12 000. Отними километр - будет 11 999. Изменилась самая правая ненулевая цифра - двойка стала единицей - и все нули правее неё превратились в девятки. Цифра слева осталась как была.

В двоичной записи то же самое, только проще: ненулевая цифра бывает одна - единица, и она становится нулём, а девятки - это единицы. Раз вычитание трогает ровно участок «младшая единица и хвост нулей под ней», его можно использовать как указатель на этот участок.

Механизм: что меняет x − 1 и что меняет −x

x      =  0101 1000
x − 1  =  0101 0111        младшая единица погашена, три нуля под ней зажжены
               ↑

Всё левее младшей единицы у x и x − 1 одинаково. Сама она и всё правее - противоположно. Теперь любая побитовая операция между x и x − 1 даёт предсказуемый результат:

x & (x − 1)   =  0101 0000     слева совпало, справа у одного из двух ноль: младшая единица убрана
x | (x − 1)   =  0101 1111     справа везде у кого-то единица: хвост нулей заполнен
x ^ (x − 1)   =  0000 1111     слева одинаково, справа различно: маска «младшая единица и хвост»
~x & (x − 1)  =  0000 0111     маска одного хвоста нулей

В последней строке x − 1 приносит единицы на место хвоста, а ~x гасит всё, что стояло единицами в самом x, - остаётся один хвост.

С минусом то же рассуждение. Из прошлой главы: -x = ~x + 1. Переворот превращает хвост нулей в хвост единиц, а младшую единицу в ноль; прибавление единицы прокатывает перенос по этим единицам, гасит их и зажигает бит на месте бывшей младшей единицы. Дальше перенос не идёт.

x      =  0101 1000
~x     =  1010 0111
−x     =  1010 1000        ниже младшей единицы - как у x, выше - всё перевёрнуто
x & −x =  0000 1000        совпали только в одном разряде

Зеркальные приёмы - для младшего нуля, через x + 1: прибавление единицы переворачивает младший ноль и хвост единиц под ним.

y            =  0101 0111
y | (y + 1)  =  0101 1111     младший ноль зажжён
y & (y + 1)  =  0101 0000     хвост единиц погашен
~y & (y + 1) =  0000 1000     одна единица на месте младшего нуля

Правило

x & (x - 1) - x без младшей единицы. x & -x - одна младшая единица x. x | (x - 1) заполняет хвост нулей единицами, x ^ (x - 1) - маска из младшей единицы и хвоста под ней. Через x + 1 то же делается с младшим нулём. Все приёмы стоят одну-две команды и работают при любом положении единицы; при x = 0 первые два дают ноль.

Разбор: номера единичных битов за число единиц

Проход по всем разрядам:

nomera = []
for k in range(52):
    if m >> k & 1:
        nomera.append(k)
print(nomera)

И проход только по единицам. mladshaya.bit_length() - 1 - номер бита единственной единицы: метод bit_length() возвращает число разрядов в записи числа, у 1000₂ это 4, а номер бита - 3.

nomera = []
while m > 0:
    mladshaya = m & -m
    nomera.append(mladshaya.bit_length() - 1)
    m = m ^ mladshaya
print(nomera)

Последняя строка цикла убирает найденную единицу; m = m & (m - 1) сделало бы то же. Для m = 2³ + 2¹⁷ + 2⁴⁴ обе программы печатают одно и то же:

[3, 17, 44]

Первая тратит 109 шагов - 52 круга независимо от содержимого. Вторая - 15 шагов, три круга. На числе, где все 52 бита единичные, вторая сделает те же 52 круга и окажется дороже первой: 211 шагов против 158, четыре шага на круг против трёх. Приём выигрывает на разреженных числах, а множества в прикладных задачах обычно такие.

Разбор: дерево Фенвика, и где приём даёт не то

В главе про дерево отрезков и дерево Фенвика формулы i & -i приняты на веру. Теперь видно, что они делают. Ячейка с номером i хранит сумму отрезка, длина которого равна младшей единице i.

def chitaet(i):
    put = []
    while i > 0:
        put.append(i)
        i = i & (i - 1)
    return put

def pravit(i, n):
    put = []
    while i <= n:
        put.append(i)
        i = i + (i & -i)
    return put

print(chitaet(13), chitaet(15), chitaet(16))
print(pravit(13, 16), pravit(1, 16))

[13, 12, 8] [15, 14, 12, 8] [16]
[13, 14, 16] [1, 2, 4, 8, 16]

Строка i = i & (i - 1) - то же, что i - (i & -i) из главы про дерево Фенвика: убрать младшую единицу. Сумма первых 13 элементов читает три ячейки: 13 = 1101₂, единиц три, и каждый круг снимает одну. Чтение стоит столько, сколько единиц в номере; у 15 = 1111₂ их четыре, у 16 - одна. Изменение элемента идёт вверх: прибавление младшей единицы даёт перенос, и младшая единица номера сдвигается влево хотя бы на разряд. Кругов в обоих циклах не больше, чем битов в n, - отсюда логарифм в цене дерева Фенвика.

Границы. Первая - ноль: у нуля младшей единицы нет, 0 & -0 равно нулю, и цикл i = i + (i & -i) от нуля не сдвинется никогда. Поэтому дерево Фенвика нумеруют с единицы.

Вторая - ширина. В 32-битном слове у числа −2³¹ единица одна, старшая, и -x равно самому x: приём по-прежнему верно выделяет её, но «противоположное число» там не существует. А x - 1 при x = 0 в 32-битном слове без знака даёт все единицы - 0 & (0 − 1) всё равно ноль, но 0 | (0 − 1) уже не ноль, а 2³² − 1.

Что ломается без этого

Первое: проверка x & -x == 1. Выделенная единица равна не единице, а своему весу: для x = 40 это 8. Сравнивать с единицей - значит проверять нечётность.

Второе: путаница убрать и оставить. x & (x - 1) и x & -x дополняют друг друга: их сумма - сам x. Перепутанные в дереве Фенвика, они дают цикл, который либо читает не те ячейки, либо не останавливается.

Третье: цикл по всем битам там, где единиц мало. Перебор подмножеств, обход соседей в графе, заданном масками, разбор набора флагов - везде внутренний цикл на 64 круга вместо двух-трёх.

Четвёртое: -x у беззнакового типа в C. Он определён и работает как надо - 2ⁿ − x. Но компилятор предупреждает о минусе у беззнакового, и «исправление» в виде приведения к знаковому на −2³¹ даёт неопределённое поведение. Безопасная запись - x & (~x + 1).

Зачем это в работе

Обход множества, записанного маской: соседи вершины в графе, свободные цифры в клетке судоку, фигуры на шахматной доске. Шахматная программа перебирает свои фигуры именно циклом «взять младшую единицу, обработать, убрать» - и делает это миллионы раз в секунду.

Дерево Фенвика целиком стоит на двух строках из разбора. А x & -x - это ещё и наибольшая степень двойки, на которую делится x: её выносят за скобку в двоичном алгоритме Евклида в уроке про длину числа.

И следующие три урока - проверка степени двойки, счёт единиц и длина числа - собраны из этого же наблюдения про вычитание единицы.

Теперь сам

1. Для x = 0110 1100 найди x & (x − 1), x & −x и x | (x − 1).
2. Сколько кругов сделает цикл «снять младшую единицу» на числе 1000?
3. Какие ячейки дерева Фенвика читает сумма первых 22 элементов?
4. Запиши одной строкой: «оставить в x только две младшие единицы». Проверь на x = 0110 1100.
5. Что даёт y & (y + 1) == 0 и для каких y оно истинно?