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

Question

我有点计数方法,我想尽快做出来.我想尝试下面的Bit Twiddling Hacks算法,但我不知道C.什么是'type T'什么是py等价于(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)存在明显的低效率:例如,'mask // 15'被计算两次.当然,这对C无关紧要,因为编译器几乎肯定会在编译时而不是运行时进行除法,但Python的窥孔优化器可能不那么聪明.

(3)最快的C方法可能无法转换为最快的Python方法.对于Python速度,您可能应该寻找一种最小化Python按位运算次数的算法.正如Alexander Gessler所说:简介!