Python-эквивалент кода C от Bit Twiddling Hacks?
У меня есть метод подсчета немного, который я пытаюсь сделать как можно быстрее. Я хочу попробовать приведенный ниже алгоритм из 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
2 ответа
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. Как сказал Александр Гесслер: профиль!
То, что вы скопировали, это шаблон для генерации кода. Не стоит транслитерировать этот шаблон на другой язык и ожидать, что он будет работать быстро. Давайте расширим шаблон.
(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
(b) старый 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
,