Python-эквивалент C-кода от Bit Twiddling Hacks?

Question

У меня есть метод подсчета битов, который я пытаюсь сделать как можно быстрее. Я хочу попробовать приведенный ниже алгоритм из Bit Twiddling Hacks , но я не знаю C. Что такое «тип T» и что эквивалент Python (T) ~ (T) 0/3?

Обобщение лучшего бита метод подсчета до целых чисел битовая ширина до 128 (параметрируется Тип T) это:

v = v - ((v >> 1) & (T)~(T)0/3);      // temp 
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT; // count

Answer 1

T - это целочисленный тип, который, я полагаю, без знака. Поскольку это C, он будет иметь фиксированную ширину, возможно (но не обязательно) одну из 8, 16, 32, 64 или 128. Фрагмент (T)~(T)0, который неоднократно появляется в этом примере кода, просто дает значение 2 ** N -1, где N - ширина типа T. Я подозреваю, что код может потребовать, чтобы N было кратным 8 для правильной работы.

Вот прямой перевод данного кода на Python, параметризованный в терминах N, ширина T в битах.

def count_set_bits(v, N=128):
    mask = (1 << N) - 1

    v = v - ((v >> 1) & mask//3)
    v = (v & mask//15*3) + ((v >> 2) & mask//15*3)
    v = (v + (v >> 4)) & mask//255*15
    return (mask & v * (mask//255)) >> (N//8 - 1) * 8

Предостережения:

(1) выше будет работать только для чисел до 2 ** 128. Вы можете обобщить его для больших чисел.

(2) Существуют очевидные недостатки: например, «маска // 15» вычисляется дважды. Конечно, для C это не имеет значения, потому что компилятор почти наверняка выполнит деление во время компиляции, а не во время выполнения, но оптимизатор глазка Python может быть не таким умным.

(3) Самый быстрый метод C вполне может не переводиться в самый быстрый метод Python. Для скорости Python вы, вероятно, должны искать алгоритм, который минимизирует количество битовых операций Python. Как сказал Александр Гесслер: профиль!

Answer 2

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

(T) ~ (T) 0 означает «столько 1-бит, сколько подходит для типа T». Алгоритму нужны 4 маски, которые мы рассчитаем для различных T-размеров, которые могут нас заинтересовать.

>>> for N in (8, 16, 32, 64, 128):
...     all_ones = (1 << N) - 1
...     constants = ' '.join([hex(x) for x in [
...         all_ones // 3,
...         all_ones // 15 * 3,
...         all_ones // 255 * 15,
...         all_ones // 255,
...         ]])
...     print N, constants
...
8 0x55 0x33 0xf 0x1
16 0x5555 0x3333 0xf0f 0x101
32 0x55555555L 0x33333333L 0xf0f0f0fL 0x1010101L
64 0x5555555555555555L 0x3333333333333333L 0xf0f0f0f0f0f0f0fL 0x101010101010101L
128 0x55555555555555555555555555555555L 0x33333333333333333333333333333333L 0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0fL 0x1010101010101010101010101010101L
>>>

Вы заметите, что маски, сгенерированные для 32-битного регистра, совпадают с масками в жестко запрограммированном 32-битном C-коде. Детали реализации: потеря суффикса L из 32-битных масок (Python 2.x) и потеря всех суффиксов L для Python 3.x.

Как видите, весь шаблон и каперсы (T) ~ (T) 0 - просто запутанная софистика. Проще говоря, для k-байтового типа вам нужно 4 маски:

k bytes each 0x55
k bytes each 0x33
k bytes each 0x0f
k bytes each 0x01

и окончательный сдвиг составляет всего N-8 (то есть 8 * (k-1)) битов. Кроме того: я сомневаюсь, что код шаблона действительно будет работать на машине, у которой CHAR_BIT не было 8, но в наши дни их не так много.

Обновление: есть еще один момент, который влияет на правильность и скорость при транслитерации таких алгоритмов с C на Python. Алгоритмы C часто предполагают целые числа без знака. В C операции над целыми числами без знака работают без вывода сообщений по модулю 2 ** N. Другими словами, сохраняются только младшие N битов. Нет исключений переполнения. Многие битовые алгоритмы полагаются на это. Однако (а) Python int и long подписаны (б) старый Python 2.X вызовет исключение, последние Python 2.X будут молча продвигать int до long и Python 3.x int == Python 2.x long.

Проблема корректности обычно требует register &= all_ones хотя бы один раз в коде Python. Тщательный анализ часто требуется для определения минимальной правильной маскировки.

Работа в long вместо int не сильно влияет на эффективность. Вы заметите, что алгоритм для 32 бит вернет ответ long даже со входа 0, потому что 32-битные all_ones long.