Степень двойки: проверить, округлить вверх, выровнять

Если ты проверишь степень двойки одной строкой и вспомнишь про ноль, округлишь 1000 вверх до степени двойки без цикла и выровняешь адрес на границу 4096, - листай до «Теперь сам».

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

Дано число. Нужно ответить, степень ли это двойки. Очевидный способ - делить на два, пока делится, и посмотреть, осталась ли единица: до 31 круга для 32-битного числа.

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

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

Круглые числа в десятичной записи: 1000 - единица и нули. Отними один - 999: цифры поменялись во всех разрядах сразу. У некруглого 1200 так не выходит: 1199, старшая единица на месте.

В двоичной записи «круглое» число - степень двойки, и только у него вычитание единицы не оставляет на месте ни одной единицы. Остальное в уроке - следствия того, что с круглыми числами деление и остаток делаются в уме: остаток от деления на 1000 - три последние цифры, частное - всё, что левее.

Механизм: одна единица, младшие биты и размазывание

Проверка. У степени двойки единица одна, значит младшая единица - она же единственная. x & (x - 1) убирает младшую единицу; если после этого остался ноль, других не было.

Деление и остаток. Число x - это (x >> k) · 2ᵏ + (k младших битов): сдвиг отрезает младшие биты, они и есть остаток.

x = 1000 = 11 1110 1000        k = 3,  2ᵏ = 8
x >> 3   = 111 1101 = 125      частное
x & 7    =      000 = 0        остаток: маска 7 = 111 - это 2ᵏ − 1

Округление до кратного. Погасить k младших битов - значит округлить вниз до кратного 2ᵏ. Маска для этого - ~(2ᵏ − 1): единицы везде, кроме k младших разрядов. Чтобы округлить вверх, сначала прибавляют 2ᵏ − 1: если число уже кратно, прибавка сгорит при гашении, если нет - перенос поднимет его до следующего кратного.

Округление до степени двойки. Нужна наименьшая степень двойки, не меньшая x. Берут x − 1 и размазывают его старшую единицу вправо, пока все разряды под ней не заполнятся. Получается 2ᵏ − 1; плюс один - степень двойки. Один шаг размазывания - x = x | x >> k: число объединяется со своей копией, сдвинутой вправо на k.

x − 1          =  0010 0100       x = 37
| сдвиг на 1   =  0011 0110       под старшей единицей - ещё одна
| сдвиг на 2   =  0011 1111       две единицы закрасили ещё два разряда
| сдвиг на 4   =  0011 1111       дальше красить нечего
+ 1            =  0100 0000       64

Каждый шаг удваивает длину сплошного блока единиц, считая от старшей: после сдвигов на 1, 2, 4, 8 и 16 в блоке 2, 4, 8, 16 и 32 единицы. Пяти сдвигов хватает на 32 бита, для 64 битов добавляют шестой - на 32. Вычитание в начале нужно, чтобы число, которое уже степень двойки, осталось собой: 64 − 1 = 63, размазывать нечего, 63 + 1 = 64.

Правило

x - степень двойки, когда x > 0 и x & (x - 1) == 0. Для делителя a = 2ᵏ: остаток - x & (a - 1), частное - x >> k, округление вниз до кратного - x & ~(a - 1), вверх - (x + a - 1) & ~(a - 1). Ближайшая сверху степень двойки - размазать старшую единицу числа x − 1 сдвигами на 1, 2, 4, 8, 16 и прибавить один; в Python то же даёт 1 << (x - 1).bit_length().

Разбор: проверка и округление вверх

def stepen_dvojki(x):
    return x > 0 and x & (x - 1) == 0

def vverh(x):
    x = x - 1
    x = x | x >> 1
    x = x | x >> 2
    x = x | x >> 4
    x = x | x >> 8
    x = x | x >> 16
    return x + 1

print(stepen_dvojki(64), stepen_dvojki(96), stepen_dvojki(1), stepen_dvojki(0))
print(vverh(1), vverh(5), vverh(64), vverh(65), vverh(1000), vverh(1000000))
print(1 << (1000 - 1).bit_length(), 1 << (64 - 1).bit_length())

True False True False
1 8 64 128 1024 1048576
1024 64

96 = 110 0000₂ - единиц две, после снятия младшей остаётся 64, не ноль. Единица - степень двойки, нулевая. Ноль - нет, и его отсекает только условие x > 0: само выражение 0 & (0 − 1) равно нулю.

vverh делает семь действий при любом x - ни цикла, ни ветвления. Последняя строка - то же самое через длину числа: (x − 1).bit_length() - сколько разрядов занимает x − 1, и единица, сдвинутая на столько, - первая степень двойки, которая в эти разряды не помещается.

Разбор: остаток маской, и где маска подводит

print(1000 & 7, 1000 % 8, 1000 >> 3, 1000 // 8)
print(1000 & ~7, 1001 + 7 & ~7, 4097 + 4095 & ~4095)
print(-13 & 7, -13 % 8)

0 0 125 125
1000 1008 8192
3 3

Вторая строка - выравнивание. Память выдаётся блоками-страницами по 4096 байтов, данные кладут по адресам, кратным 8 или 16, и число часто нужно округлить до такой границы. 1000 уже кратно восьми, 1001 поднимается до 1008, а 4097 байтов занимают две страницы памяти по 4096. Сложение сильнее &, поэтому 1001 + 7 & ~7 - это (1001 + 7) & ~7.

Третья строка - про отрицательные числа. Маска даёт остаток 3, и в Python % даёт столько же. В C и Java -13 % 8 равно −5: там остаток берёт знак делимого, и замена % на & меняет ответ. Компилятор C, встретив x % 8 для знакового x, не может поставить одну маску и дописывает поправку на знак.

Теперь главная область применения и её ловушка. Индекс в хеш-таблице размером 2ᵏ - это hesh & (razmer - 1): одна команда вместо деления. Так устроены словарь в Python и HashMap в Java. Но маска смотрит только на младшие биты хеша. Старшие в выборе ячейки не участвуют вовсе:

хеши 0x10000, 0x20000, 0x30000, ...     таблица на 16 ячеек:  хеш & 15 = 0 у всех

Все ключи попали в одну ячейку. В разделе про хеширование для метода деления брали простой размер таблицы как раз затем, чтобы на остаток влияли все биты. Таблица со степенью двойки платит за скорость обязанностью перемешать хеш заранее: HashMap перед маской считает h ^ (h >> 16), подмешивая старшую половину в младшую; именно ^, потому что | только зажигал бы биты и склеивал разные хеши. Для 0x9E3779B9 и таблицы на 16 ячеек индекс без перемешивания - 9, с перемешиванием - 14.

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

Первое: ноль - степень двойки. Проверка без x > 0 пропускает ноль, и следом идёт сдвиг на «номер единственного бита», которого нет.

Второе: маска для не-степени. x & (10 - 1) не равно x % 10: маска 1001₂ вырезает два несвязанных бита. Приём работает только для делителя с единственной единицей, и перед заменой % на & это проверяют той самой строкой.

Третье: округление вверх переполняется. В C для x больше 2³¹ в 32-битном слове ближайшей сверху степени двойки нет, и такая функция возвращает ноль. В Python показанная vverh верна до 2³², а дальше ей не хватает шестого сдвига. vverh(0) возвращает ноль везде: 0 − 1 - все единицы, плюс один - ноль.

Четвёртое: (x + a - 1) у самого края. Выравнивание адреса у верхней границы типа переполняется ещё до маски. В ядрах операционных систем это отдельная проверка.

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

Кольцевой буфер размером 2ᵏ: индекс следующего элемента - (i + 1) & (razmer - 1), без сравнения с концом и без деления. Поэтому размеры очередей и буферов в сетевых стеках и аудиотрактах - степени двойки.

Выделение памяти: размер запроса округляют вверх до кратного 16 байтам маской, а большие блоки берут целыми страницами - округляют вверх до кратного 4096. Динамический массив из раздела про амортизацию удваивает вместимость, и вместимость «не меньше n» - это vverh(n).

Быстрое преобразование Фурье в варианте из раздела «Разделяй и властвуй» требует длину, равную степени двойки: вход дополняют нулями до vverh(n). Нерекурсивное дерево отрезков строят на vverh(n) листьях по той же причине - у полного двоичного дерева число листьев круглое.

Теперь сам

1. Степень ли двойки число 4096? А 4100? Проверь выражением.
2. Найди 1000 & 63 и скажи, остаток от деления на что это.
3. Округли 5000 вверх до кратного 4096 и вниз до кратного 1024.
4. Проследи vverh(100): чему равно x после каждого из пяти сдвигов?
5. Таблица на 64 ячейки, ключи - числа, кратные 64. Что будет с индексами hesh & 63 и чем лечить?