Python 相当于 Bit Twiddling Hacks 中的 C 代码？

我有一个位计数方法，我正在尝试尽可能快地实现。我想尝试下面的算法位摆弄黑客 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel，但我不知道 C。什么是“类型 T”以及 (T)~(T)0/3 的 python 等价物是什么？

最好的概括 整数的计数方法 位宽高达 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

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

Caveats:

(1) 以上仅适用于 2**128 以内的数字。不过，您也许可以将其推广到更大的数字。

(2)存在明显的低效率：例如，'mask//15'被计算了两次。当然，这对于 C 来说并不重要，因为编译器几乎肯定会在编译时而不是运行时进行除法，但 Python 的窥孔优化器可能没那么聪明。

(3) 最快的 C 方法很可能无法转化为最快的 Python 方法。为了提高 Python 速度，您可能应该寻找一种能够最大限度地减少 Python 按位运算数量的算法。正如亚历山大·盖斯勒所说：个人资料！