Python等价的C代码？

Question

我有一个点计数的方法，我正在努力使尽可能快。我想从Bit Twiddling Hacks开始尝试下面的算法，但是我不知道C。什么是'typet'，什么是python等价的（t）~（t）0/3？在

A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this:

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）～（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代码中的掩码匹配。实现细节：丢失32位掩码（python2.x）中的L后缀，并丢失python3.x的所有L后缀

如你所见，整个模板和（T）~（T）0 caper只是模糊的诡辩。简单地说，对于k字节类型，需要4个掩码：

^{pr2}$

最后的移位仅仅是N-8（即8*（k-1））位。旁白：我怀疑模板代码是否真的能在字符位不是8的机器上运行，但是现在这种代码并不多。在

更新：在将这样的算法从C翻译成Python时，还有另一点会影响正确性和速度。C算法通常假设无符号整数。在C语言中，对无符号整数的运算是静默模2**N。换句话说，只保留最低有效的N位。没有溢出异常。许多位旋转算法都依赖于此。但是（a）Python的int和long是有符号的（b）旧的python2.X将引发一个异常，最近的python2.Xs将静默地将int升级为long，python3.Xint==Python 2.Xlong。在

在Python代码中，正确性问题通常至少需要register &= all_ones一次。通常需要仔细分析以确定最小的正确掩蔽。在

工作在long而不是{}对效率没有多大帮助。您会注意到，32位的算法将返回一个long答案，即使是从0的输入中，因为32位的所有1都是long。在

Answer 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）存在明显的低效率：例如，“mask//15”计算了两次。当然，这对C来说并不重要，因为编译器几乎肯定会在编译时而不是运行时进行除法，但是Python的peephole优化器可能并不那么聪明。在

（3）最快的C方法很可能不会转化为最快的Python方法。为了提高Python的速度，您可能应该寻找一种能够最小化Python按位操作数的算法。正如亚历山大·盖斯勒所说：侧写！在