Bitcounting可以通过多种方式完成,例如. with set bit iterator,unset bit iterator,pre-computed bits with lookup tables或parallel counting.正如我通过搜索网络所发现的那样,当未设置的位数较少时,未设置的位迭代器很快,而相反的位置则设置位迭代器.但是什么时候应该使用并行计数,特别是MIT HAKMEM(见下文)？它似乎相当快,虽然可能比查找表慢.在速度方面,它与set / unset位相比总是更好吗？还有其他一些关于速度和记忆的选择吗？
int BitCount(unsigned int u) {
unsigned int uCount;
uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}
解决方法
为什么选择一种比特计数法呢？那真的取决于你的机器和你想要解决的问题.请注意,我在下面给出的所有指令计数都是针对基本的RISC处理器,并且可能无法很好地转换为像x86这样的更复杂的野兽.
您引用的HAKMEM算法将在13条指令中执行,但由于模数运算符,它不太可能非常快.通过引人注目,它看起来确实具有一些非常好的指令级并行性,如果你的处理器能够利用它,它应该会有所帮助.
Bo PeRSSon提出的算法非常快(2 5 * pop(x)指令),但前提是这个词是稀疏填充的.它也可以修改为适用于人口稠密的单词.它还包含分支,并且没有任何重要的指令级并行性.
编辑：表查找方法也可以非常快,但确实进行内存访问.如果整个表都在L1缓存中,那么它可能是最快的算法之一.如果表不在缓存中,那么它几乎肯定是最慢的.
下面的算法是HAKMEM算法之一的变体,并在Hacker’s Delight书中提出(如果你喜欢这类东西,我强烈推荐这本书).它以19条指令执行,并且是无分支的.它也不使用除法,但确实有乘法.通过尽可能多地重复使用相同的掩码来使用寄存器的方式也非常经济.我在这里仍然没有明显的指令级并行性.
int pop(unsigned x) {
unsigned n;
n = (x >> 1) & 0x77777777;
x = x - n;
n = (n >> 1) & 0x77777777;
x = x - n;
n = (n >> 1) & 0x77777777;
x = x - n;
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x * 0x01010101;
return x >> 24;
}
Hacker’s Delight书还为9-8-7位宽字段或使用浮点运算符提供了一些更专业的算法.请注意,我上面提到的大多数分析也部分取自该书.
事实是,有一种卡车装载的方法,唯一的方法是确保哪种方法在您的特定情况下最有效,就是测量和比较.我确实意识到这是一个很好的解决方案,但另一种方法是了解你的处理器和编译器.
