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,

Другие вопросы по тегам