Длина числа, ведущие и хвостовые нули: логарифм за пять сравнений

Если ты найдёшь ⌊log₂ x⌋ и ⌈log₂ x⌉ через длину числа, напишешь поиск старшей единицы делением пополам и скажешь, чему равно число хвостовых нулей у 40, - листай до «Теперь сам».

Как думаешь, за сколько сравнений находится старшая единица

В 32-битном числе нужно найти номер старшей единицы. Цикл сдвигает число вправо, пока оно не станет нулём, - до 32 кругов.

Прежде чем читать дальше, вспомни игру «угадай число от 1 до 32» и ответь себе, сколько вопросов в ней нужно. Столько же сравнений хватит и здесь: пять.

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

Здание неизвестной высоты, не выше 32 этажей, и нужно узнать, сколько в нём этажей. Можно подниматься по лестнице, считая. А можно спрашивать: «выше шестнадцатого что-нибудь есть?» Если да - нижние шестнадцать можно не считать, они точно есть, и вопрос повторяется про верхнюю половину. Если нет - про нижнюю. Каждый вопрос делит оставшуюся неизвестность пополам.

Вопрос «есть ли что-нибудь выше этажа 16» для числа - это сравнение x >> 16 с нулём.

Механизм: одна величина и четыре её имени

Пусть длина числа x - число разрядов в его двоичной записи без ведущих нулей. У 1000₂ длина 4, у нуля - 0.

x = 40 = 0000 0000 0010 1000        слово в 16 битов

ведущие нули      0000 0000 00              10 штук
длина                         10 1000       6 разрядов: от старшей единицы до правого края
хвостовые нули                    000       3 штуки: правее младшей единицы

От длины считаются четыре величины.

Целый логарифм. ⌊log₂ x⌋ - сколько раз x делится пополам, пока не станет единицей. Каждое деление пополам - сдвиг вправо на разряд, и до единицы их нужно длина − 1. Для 40 это 5: 2⁵ = 32 ≤ 40 < 64.

Логарифм с округлением вверх. ⌈log₂ x⌉ - наименьшее k, для которого 2ᵏ ≥ x. Это длина числа x − 1: у 40 - длина 39, то есть 6; у 32 - длина 31, то есть 5. Причина: числа от 2ᵏ⁻¹ + 1 до 2ᵏ после вычитания единицы лежат от 2ᵏ⁻¹ до 2ᵏ − 1 и имеют длину ровно k.

Ведущие нули в слове ширины w - w − длина.

Хвостовые нули - номер младшей единицы. Из первого урока главы: x & -x оставляет одну эту единицу, и её номер - её длина минус один. У 40 это 3, и 2³ = 8 - наибольшая степень двойки, на которую 40 делится.

Теперь сама длина без цикла по битам. Двоичный поиск по разрядам: если в старших 16 битах что-то есть, длина не меньше 16 - запоминаем 16 и дальше смотрим только на старшую половину. Потом то же для 8, 4, 2 и 1.

Правило

Длина L числа x - номер старшей единицы плюс один; у нуля L = 0. Тогда ⌊log₂ x⌋ = L − 1, ведущих нулей в слове из w битов - w − L, ⌈log₂ x⌉ - длина числа x − 1. Хвостовых нулей - длина(x & -x) − 1. Для нуля логарифм и число хвостовых нулей не определены. В Python длина - x.bit_length().

Разбор: длина делением пополам

def dlina(x):
    n = 0
    if x >> 16 > 0:
        n = n + 16
        x = x >> 16
    if x >> 8 > 0:
        n = n + 8
        x = x >> 8
    if x >> 4 > 0:
        n = n + 4
        x = x >> 4
    if x >> 2 > 0:
        n = n + 2
        x = x >> 2
    if x >> 1 > 0:
        n = n + 1
        x = x >> 1
    return n + x

for x in [1, 5, 255, 256, 1000000, 0xFFFFFFFF, 0]:
    print(x, dlina(x), x.bit_length())

1 1 1
5 3 3
255 8 8
256 9 9
1000000 20 20
4294967295 32 32
0 0 0

Проследи x = 1 000 000. В старших 16 битах есть единицы: n = 16, остаётся 1000000 >> 16 = 15. 15 >> 8 и 15 >> 4 - нули, эти два условия не срабатывают. 15 >> 2 = 3 - не ноль: n = 18, остаётся 3. 3 >> 1 = 1 - не ноль: n = 19, остаётся 1. Ответ 19 + 1 = 20. Последнее слагаемое - сам остаток, ноль или единица: оно и отличает ноль от единицы.

На двухстах случайных 32-битных числах цикл со сдвигом по одному разряду стоит 19 578 шагов, деление пополам - 3 548: около 98 и 18 шагов на число, считая вызов функции и присваивания. И для миллиона всё вместе:

x = 1000000
print(x.bit_length() - 1, (x - 1).bit_length(), 32 - x.bit_length(), (x & -x).bit_length() - 1)

19 20 12 6

2¹⁹ = 524 288 ≤ 1 000 000 < 2²⁰. В 32 битах перед числом 12 нулей. А шесть хвостовых нулей - это 1 000 000 = 2⁶ · 15 625: миллион - это 10⁶, в нём шесть двоек и шесть пятёрок.

Разбор: Евклид без деления, и где он проигрывает

Хвостовые нули позволяют считать наибольший общий делитель одними сдвигами и вычитаниями. Три наблюдения: общую степень двойки можно вынести за скобку; двойку, которая есть только у одного из чисел, можно выбросить - в общий делитель она не входит; разность двух нечётных чисел чётна, и НОД от замены большего на разность не меняется.

def nod_dvoichnyj(a, b):
    if a == 0:
        return [b, 0]
    if b == 0:
        return [a, 0]
    sdvig = ((a | b) & -(a | b)).bit_length() - 1
    a = a >> (a & -a).bit_length() - 1
    krugov = 0
    while b != 0:
        b = b >> (b & -b).bit_length() - 1
        if a > b:
            t = a
            a = b
            b = t
        b = b - a
        krugov = krugov + 1
    return [a << sdvig, krugov]

print(nod_dvoichnyj(1989, 867), nod_dvoichnyj(48, 180))
print(nod_dvoichnyj(832040, 514229), nod_dvoichnyj(1000000007, 998244353))

[51, 5] [12, 4]
[1, 14] [1, 22]

sdvig - число хвостовых нулей у a | b, то есть общая степень двойки: у a | b младшая единица стоит там, где она впервые появляется хотя бы у одного. Внутри цикла a всегда нечётно, из b выбрасываются двойки, большее заменяется разностью.

Сравни с алгоритмом Евклида на остатках из раздела про числа:

пара                          двоичный     на остатках
1989 и 867                    5 кругов     4 круга
832 040 и 514 229            14 кругов    28 кругов
1 000 000 007 и 998 244 353  22 круга      9 кругов

Вторая пара - соседние числа Фибоначчи, худший вход для остатков; двоичный вариант проходит его вдвое быстрее. На третьей он проигрывает в два с половиной раза. По числу кругов победителя нет, и граница приёма в другом: в круге двоичного алгоритма нет деления, только сдвиг, сравнение и вычитание. На процессорах, где деление в десятки раз дороже вычитания, и на длинных числах, где деление - отдельный сложный алгоритм, он выгоднее при том же или большем числе кругов.

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

Первое: ноль. У нуля нет ни старшей, ни младшей единицы. (0).bit_length() - 1 равно −1, и следом идёт сдвиг на отрицательное число - Python остановит программу с ошибкой. В C хуже: результат функции числа ведущих нулей __builtin_clz(0) не определён и на разных процессорах получается разным. Ноль проверяют до вызова.

Второе: логарифм через дробные числа. int(math.log2(x)) выглядит естественно и врёт на больших числах: для x = 2⁴⁹ − 1 получается 49, хотя старшая единица стоит в бите 48. Само x в дробное число помещается; не помещается его логарифм - он меньше 49 на величину, которой в 53 значащих битах нет места, и округляется до ровного 49,0. x.bit_length() - 1 точен при любой длине.

Третье: округление вверх через длина(x). Для степени двойки ⌈log₂ x⌉ = ⌊log₂ x⌋, и длина самого x даёт на единицу больше. Нужна длина x − 1.

Четвёртое: длина отрицательного. В Python (-5).bit_length() равно 3 - метод смотрит на модуль. В слове фиксированной ширины у отрицательного числа старший бит - единица, и длина равна ширине.

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

Разреженная таблица из главы про запросы к дереву отвечает на запрос минимума на отрезке длины d двумя блоками длины 2ᵏ, где k = ⌊log₂ d⌋. Это d.bit_length() - 1, и таблица заранее посчитанных логарифмов, которую для этого часто заводят, не нужна. Уровень узла с номером i в двоичной куче с нумерацией от единицы - тоже i.bit_length() - 1.

Кодировка UTF-8 записывает длину символа числом ведущих единиц первого байта: 110… - два байта, 1110… - три. Декодер считает ведущие нули у байта, обращённого операцией ~. Планировщик задач держит битовую карту непустых очередей по приоритетам и находит самую приоритетную поиском первой единицы - за одну команду при любом числе очередей.

Команды называются LZCNT и TZCNT в x86 и CLZ в ARM. В C++ - std::countl_zero, std::countr_zero и std::bit_width, в C - stdc_leading_zeros и stdc_trailing_zeros.

Теперь сам

1. Найди длину, ⌊log₂ x⌋ и ⌈log₂ x⌉ для x = 100.
2. Сколько ведущих нулей у числа 1000 в 16-битном слове?
3. Сколько хвостовых нулей у 96 и на какую наибольшую степень двойки оно делится?
4. Проследи dlina(300): какие из пяти условий сработают?
5. Отрезок длины 13 покрывают двумя блоками длины 2ᵏ. Чему равно k и почему блоков хватает двух?