位操作:计算uint64_t中所有位(也就是1的数)的和

Question

在C++中,我想计算a中1的位数 uint64_t

# A few examples in uint8_t:
0b00000000  ==> 0
0b01000001  ==> 2
0b00110101  ==> 4
0b11111111  ==> 8

我需要执行很多(比如数百万)这样的操作,有没有快速的方法(可能有一些预处理)？

我能想到的一种可能性是为每个N位创建一个查找表(比方说N=8),并64/N为a 执行查找uint64_t.有更好的解决方案吗？如果我决定采用上述方法,我应该如何设置N？(根据我的理解,甚至忽略了所有的预处理计算,情况并不是越大N越好,因为查找速度实际上取决于查找表是否适合缓存？)

非常感谢!

Answer 1

最快的方法是__builtin_popcountll使用GCC和Clang以及_mm_popcnt_u64VC++.
当使用适当的标志(例如-march=native)进行编译时,这将产生最佳性能,因为内在函数被简化为与SSE 4.2一起引入的汇编指令POPCNT.演示.

如果这不适用,请尝试使用查找表进行一次使用Hack.