Счёт единиц: по битам, по единицам, по таблице и половинками

Если ты напишешь цикл, который считает единицы за число единиц, объяснишь, зачем в сложении половинками маски 0x55555555 и 0x33333333, и скажешь, какой способ выбрать для разреженных чисел, - листай до «Теперь сам».

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

Дано 32-битное число, нужно количество единичных битов в нём. Цикл по битам очевиден: до 32 кругов. Цикл по единицам из урока про младшую единицу лучше, но на числе из одних единиц это те же 32 круга.

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

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

Подсчёт голосов на выборах. Можно свезти все бюллетени в одну комнату и считать по одному. А можно иначе: каждый участок считает у себя, соседние участки складывают итоги в районный, районы - в областной. Этажей мало, и на каждом этаже все складывают одновременно.

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

Механизм: четыре способа

По битам. Смотреть младший бит, сдвигать вправо. Кругов столько, сколько разрядов до старшей единицы.

По единицам. x = x & (x - 1) снимает младшую единицу. Кругов столько, сколько единиц.

По таблице. Заранее посчитать число единиц для всех 256 значений байта, потом разрезать слово на четыре байта и сложить четыре числа из таблицы. Саму таблицу строят за один проход: у числа i единиц столько же, сколько у i >> 1, плюс младший бит.

Половинками. Слово читается как 16 пар битов. В каждой паре нужно получить число единиц - от 0 до 2, оно как раз помещается в два бита. Потом как 8 четвёрок, в каждой сумма двух пар - от 0 до 4. Потом как 4 байта, в каждом сумма двух четвёрок.

x                       =  1 1 0 1 0 1 1 0       восемь битов, единиц пять
пары:     x − (x >> 1 & 0101 0101)
                        =  10  01  01  01        в парах 2, 1, 1, 1
четвёрки: (x & 0011 0011) + (x >> 2 & 0011 0011)
                        =  0011    0010          в четвёрках 3 и 2
байт:     x + (x >> 4) & 0000 1111
                        =  0000 0101             5

В каждой строке схемы x - результат предыдущей строки. Маска 0101… - это 0x55555555, она оставляет младший бит каждой пары. Маска 0011… - 0x33333333, младшую пару каждой четвёрки. 0x0F0F0F0F - младшую четвёрку каждого байта. Сдвиг подводит старшую половину ячейки под младшую, маска не даёт соседним ячейкам смешаться.

Первая строка записана хитрее остальных. Пара битов a b как число равна 2a + b, а нужна сумма a + b. Разница - ровно a, то есть старший бит пары, подведённый сдвигом под младший: (2a + b) − a.

Правило

Число единиц: циклом x = x & (x - 1) - за число единиц; таблицей на 256 значений - за число байтов; сложением половинками - за шесть действий на 32 бита при любом x. Маски половинок - 0x55555555, 0x33333333, 0x0F0F0F0F. Все способы рассчитаны на неотрицательное число известной ширины. В Python - x.bit_count(), в C++ - std::popcount, в C - stdc_count_ones.

Разбор: сложение половинками на 32 битах

def polovinkami(x):
    x = x - (x >> 1 & 0x55555555)
    x = (x & 0x33333333) + (x >> 2 & 0x33333333)
    x = x + (x >> 4) & 0x0F0F0F0F
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x3F

print(polovinkami(0b11010110), polovinkami(0xFFFFFFFF), polovinkami(0x80000001), polovinkami(0))

5 32 2 0

После третьей строки в каждом байте лежит число единиц этого байта - от 0 до 8. Четвёртая и пятая складывают байты между собой уже без масок: сумма не больше 32 и в байт помещается, а мусор в старших байтах срезает последняя маска 0x3F - шесть битов, которых хватает для числа 32.

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

Разбор: замер четырёх способов, и чего замер не видит

Двести 32-битных чисел, полученных генератором. Плотные - случайные, в среднем по 16 единиц. Разреженные - с единицей в старшем бите и ещё двумя в случайных местах, в среднем по 2,9 единицы.

def po_bitam(x):
    n = 0
    while x > 0:
        n = n + (x & 1)
        x = x >> 1
    return n

def po_edinicam(x):
    n = 0
    while x > 0:
        x = x & (x - 1)
        n = n + 1
    return n

tablica = [0] * 256
for i in range(1, 256):
    tablica[i] = tablica[i >> 1] + (i & 1)

def po_tablice(x):
    return tablica[x & 255] + tablica[x >> 8 & 255] + tablica[x >> 16 & 255] + tablica[x >> 24]

po_tablice рассчитана на число не шире 32 битов: у более длинного x >> 24 выйдет за таблицу.

способ                 плотные    разреженные
по битам                19 578       20 202
по единицам             10 467        2 739
половинками              1 602        1 602
по таблице                 602          602
x.bit_count()              402          402

Цикл по битам не зависит от числа единиц, но зависит от положения старшей. Цикл по единицам на разреженных числах дешевле цикла по битам в семь раз. Таблица и половинки не зависят ни от чего. Построение таблицы - 767 шагов, из них 256 на создание списка, - в замер не вошло: это разовая цена.

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

Команда счёта единиц есть в процессорах x86 с 2007-2008 годов и называется POPCNT; с ней все способы выше - запасной вариант для машин без неё. Метод bit_count() появился в Python 3.10.

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

Первое: отрицательное число в цикле. Показанные циклы для отрицательного x сразу возвращают ноль: условие x > 0 ложно. С условием x != 0 было бы хуже: у отрицательного числа в Python бесконечно много единиц слева, x & (x - 1) снимает их по одной и до нуля не доходит. Сначала маска нужной ширины - x & 0xFFFFFFFF.

Второе: чужая ширина. Маски 0x55555555 - на 32 бита. 40-битное число пройдёт через функцию без ошибки и вернёт неверный ответ: старшие биты пропадут на масках. Для 64 битов все константы удваивают по длине, добавляют строку со сдвигом на 32, а последнюю маску берут 0x7F.

Третье: забытая последняя маска. Без & 0x3F функция возвращает число, в старших байтах которого лежат промежуточные суммы.

Четвёртое: bin(x).count("1"). Работает, но строит строку длиной с число и проходит её посимвольно. В Python до 3.10 это был самый быстрый способ - и хороший пример того, как отсутствие нужной команды искажает код.

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

Длина префикса по маске подсети - число единиц в ней: у 255.255.255.192 их 26, отсюда /26. Расстояние Хэмминга из прошлой главы - счёт единиц в a ^ b.

Сжатые структуры данных хранят вместо массива из 32 указателей битовую карту «какие из 32 ячеек заняты» и плотный массив только занятых. Место ячейки k в плотном массиве - число единиц в карте ниже бита k: (karta & (1 << k) - 1).bit_count(). Так устроены неизменяемые словари в Clojure и Scala, и счёт единиц там выполняется на каждом шаге поиска.

Чётность числа единиц - младший бит счёта, x.bit_count() & 1. Бит чётности - простейшая проверка целостности: он ловит любую одиночную ошибку при передаче байта.

Теперь сам

1. Сколько кругов сделает цикл по единицам и цикл по битам на числе 0x8001?
2. Проведи первые две строки сложения половинками для x = 1011 0100.
3. Чему равно tablica[13] и как оно получается из tablica[6]?
4. В карте 0b10110100 занята ячейка 5. Какой у неё номер в плотном массиве?
5. Числа приходят с тремя-четырьмя единицами из 64. Какой из способов без встроенной команды ты возьмёшь?