# конспект · шаг 8 из 8
Конспект: счёт единиц, младший бит, степень двойки
Понятия
Младшая единица - самый правый единичный бит числа. Вычитание единицы переворачивает её и все нули под ней.
Длина числа - число разрядов двоичной записи: номер старшей единицы плюс один. У нуля длина 0.
Ведущие нули - нули слева от старшей единицы в слове; хвостовые нули - нули справа от младшей.
SWAR - слово как ряд независимых полей, которые обрабатываются одной командой.
Порядок байтов - какой байт числа лежит по младшему адресу: младший (x86, ARM) или старший (сеть).
Что унести
СЕМЕЙСТВО МЛАДШЕЙ ЕДИНИЦЫ x = 0101 1000
x & (x − 1) убрать её 0101 0000
x & −x оставить только её 0000 1000
x | (x − 1) заполнить хвост нулей 0101 1111
x ^ (x − 1) маска «она и хвост» 0000 1111
~x & (x − 1) маска хвоста 0000 0111
ТО ЖЕ ДЛЯ МЛАДШЕГО НУЛЯ y = 0101 0111
y | (y + 1) зажечь его 0101 1111
y & (y + 1) погасить хвост единиц 0101 0000
ОБХОД ЕДИНИЧНЫХ БИТОВ ДЕРЕВО ФЕНВИКА
пока m > 0: сумма первых i: i = i & (i − 1) 13 → 12 → 8
e = m & −m изменение i: i = i + (i & −i) 13 → 14 → 16
номер = e.bit_length() − 1 нумерация с единицы: у нуля младшей единицы нет
m = m ^ e
три единицы из 52 битов: 15 шагов против 109; все 52 единицы: 211 против 158
СТЕПЕНЬ ДВОЙКИ, a = 2ᵏ
проверка x > 0 and x & (x − 1) == 0 ноль проходит без x > 0
остаток x & (a − 1) 1000 & 7 = 0
частное x >> k 1000 >> 3 = 125
вниз до кратного x & ~(a − 1) 5000 & ~1023 = 4096
вверх до кратного (x + a − 1) & ~(a − 1) (5000 + 4095) & ~4095 = 8192
вверх до степени 1 << (x − 1).bit_length() 1000 → 1024, 64 → 64
без метода: x − 1, затем x |= x >> 1, 2, 4, 8, 16, затем + 1
индекс в таблице hesh & (razmer − 1) только младшие биты: мешать h ^ (h >> 16)
| счёт единиц, 200 чисел по 32 бита | плотные | разреженные | от чего зависит |
|---|---|---|---|
| цикл по битам | 19 578 | 20 202 | положение старшей единицы |
цикл x = x & (x - 1) |
10 467 | 2 739 | число единиц |
| половинками, 6 строк | 1 602 | 1 602 | ничего |
| таблица на 256 | 602 | 602 | ничего; на деле - кеш |
x.bit_count() |
402 | 402 | ничего |
ПОЛОВИНКАМИ, 32 бита
x = x − (x >> 1 & 0x55555555) пары: 2a + b − a = a + b
x = (x & 0x33333333) + (x >> 2 & 0x33333333) четвёрки: маска ДО сложения
x = x + (x >> 4) & 0x0F0F0F0F байты: маска после, 8 помещается в 4 бита
x = x + (x >> 8); x = x + (x >> 16); x & 0x3F
ДЛИНА L = x.bit_length() x = 1 000 000
⌊log₂ x⌋ = L − 1 19
⌈log₂ x⌉ = (x − 1).bit_length() 20
ведущих нулей в w битах = w − L 12 при w = 32
хвостовых нулей = (x & −x).bit_length() − 1 6: 10⁶ = 2⁶ · 15 625
без метода: двоичный поиск по разрядам - пять сравнений (16, 8, 4, 2, 1), 3 548 шагов против 19 578
ДВОИЧНЫЙ ЕВКЛИД: вынести общую степень двойки, выбрасывать двойки у каждого, большее заменять разностью
1989 и 867: 5 кругов (на остатках 4) Фибоначчи 832 040 и 514 229: 14 (28)
1 000 000 007 и 998 244 353: 22 (9) выигрыш не в кругах, а в отсутствии деления
НУЛЕВОЙ БАЙТ В СЛОВЕ (x − 0x01010101) & ~x & 0x80808080 ≠ 0
41 00 43 44 → 00 80 00 00 байт c ищут в x ^ (c · 0x01010101)
младший флажок честный, старшие могут быть ложными: 00 FF 01 00 → 80 00 80 80
длина строки в 407 символов: 217 шагов против 817
РАЗВОРОТ: обмен соседних полей x = (x & M) << s | x >> s & M
биты: M = 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF; s = 1, 2, 4, 8, 16
байты: только два последних шага 0xC0A8011E ↔ 0x1E01A8C0
Команды и функции. Счёт единиц - POPCNT, std::popcount, stdc_count_ones, bit_count() с Python
3.10. Нули по краям - LZCNT, TZCNT, std::countl_zero, std::countr_zero. Разворот байтов - BSWAP,
htonl.
Ловушки джокера
x & -x == 1. Выделенная единица равна своему весу: для 40 это 8.
Ноль. Проходит проверку степени двойки, не имеет ни логарифма, ни хвостовых нулей;
__builtin_clz(0) в C не определён. Цикл Фенвика от нуля не сдвигается.
Отрицательное число в цикле по единицам. В Python единиц слева бесконечно: цикл с условием x != 0
не останавливается, с x > 0 молча возвращает ноль.
Маска для не-степени. x & 9 - не остаток от деления на 10.
% на & для знаковых в C. -13 % 8 там −5, а -13 & 7 равно 3.
Чужая ширина. 40-битное число в функции с масками на 32 бита молча теряет старшие биты.
Логарифм через дробные. int(math.log2(2⁴⁹ − 1)) равно 49, верный ответ 48.
⌈log₂ x⌉ через длину x. Для степени двойки выходит на единицу больше; нужна длина x − 1.
Число флажков как число нулевых байтов. Байт 01 над нулевым получает ложный флажок.
Чтение слова за концом строки. Через границу страницы памяти, если следующая не выдана, - аварийная остановка; сначала выравнивают адрес.
Разворот битов вместо разворота байтов. При смене порядка байтов биты внутри байта стоят на месте.
Куда это ведёт
Все приёмы главы заменяли цикл по разрядам несколькими командами. Следующая глава заменяет другое -
ветвление и деление: модуль числа и минимум двух чисел без if, среднее без переполнения, деление на
константу умножением. Инструмент прежний - маска, только теперь её делают из знакового бита.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий