代表数字7的8位看起来像这样：
00000111
设置了三个位。
确定32位整数中的置位位数的算法是什么？
最佳答案
这称为“ Hamming Weight”，“ popcount”或“ sideways加法”。
“最佳”算法实际上取决于您所使用的CPU以及您的使用模式。
一些CPU具有单个内置指令来执行此操作，而其他CPU具有作用于位向量的并行指令。并行指令（如x86的popcnt，在受支持的CPU上）几乎可以肯定是最快的。其他一些体系结构的慢速指令可以通过微编码循环来实现，该循环每个周期测试一位（需要引用）。
如果您的CPU具有较大的缓存，并且/或者您正在紧凑的循环中执行大量这些指令，那么预填充的表查找方法可能会非常快。但是，由于“高速缓存未命中”的代价，它可能会遭受损失，在这种情况下，CPU必须从主内存中获取某些表。
如果您知道字节将大部分为0或大多数为1，那么对于这些情况，有非常有效的算法。
我相信以下是一种非常好的通用算法，称为“并行”或“可变精度SWAR算法”。我已经用类似C的伪语言表示了这一点，您可能需要对其进行调整以使其适用于特定语言（例如，对于C ++使用uint32_t，而在Java中使用>>>）：
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
这是所讨论的所有算法中最坏情况下的行为，因此可以有效地处理您使用的所有使用模式或值。
这种逐位SWAR算法可以并行化以一次在多个矢量元素中完成，而不是在单个整数寄存器中完成，以提高具有SIMD但没有可用的popcount指令的CPU的速度。 （例如x86-64代码必须在任何CPU上运行，而不仅仅是Nehalem或更高版本。）
但是，将向量指令用于popcount的最佳方法通常是通过使用变量改组在每个字节并行的同时对4位进行表查找。 （这4位索引了保存在向量寄存器中的16个条目表）。
在Intel CPU上，硬件64位popcnt指令的性能比SSSE3
PSHUFB bit-parallel implementation高2倍左右，但只有if your compiler gets it just right。否则，上证所可能会明显领先。较新的编译器版本知道popcnt false dependency problem on Intel。参考文献：
https://graphics.stanford.edu/~seander/bithacks.html
https://en.wikipedia.org/wiki/Hamming_weight
http://gurmeet.net/puzzles/fast-bit-counting-routines/
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)
关于algorithm - 如何计算32位整数中的设置位数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6004614/