代表数字 7 的 8 位如下所示：
00000111
设置了三位。
确定 32 位整数中设置位数的算法是什么？
这被称为“汉明权重”、“popcount”或“横向加法”。
一些 CPU 有一个内置指令来执行此操作，而另一些 CPU 具有作用于位向量的并行指令。像 x86 的指令popcnt（在支持它的 CPU 上）几乎可以肯定对于单个整数来说是最快的。其他一些架构可能有一个缓慢的指令，它使用一个微编码循环来实现，每个周期测试一个位（ 需要引用 - 如果硬件popcount存在的话，它通常很快。）。
popcnt
“最佳”算法实际上取决于您使用的 CPU 以及您的使用模式。
您的编译器可能知道如何为您正在编译的特定 CPU 做一些有益的事情，例如C++20std::popcount()或 C++ std::bitset<32>::count()，作为访问内置/内在函数的可移植方式（请参阅有关此问题的另一个答案）。但是您的编译器为没有硬件 popcnt 的目标 CPU 选择的后备可能不是您的用例的最佳选择。或者您的语言（例如 C）可能不会公开任何可以使用特定于 CPU 的 popcount 的可移植函数。
std::popcount()
std::bitset<32>::count()
如果您的 CPU 有一个大缓存并且您在一个紧密的循环中执行大量这些操作，那么预填充的表查找方法可能会非常快。然而，由于“缓存未命中”的代价，它可能会受到影响，其中 CPU 必须从主内存中获取一些表。（分别查找每个字节以保持表格较小。）如果您希望 popcount 用于连续范围的数字，则只有低字节会改变 256 个数字的组，这非常好。
如果您知道您的字节大部分为 0 或大部分为 1，那么对于这些场景有有效的算法，例如在循环中使用 bithack 清除最低集，直到它变为零。
我相信一个非常好的通用算法如下，称为“并行”或“可变精度 SWAR 算法”。我已经用类似 C 的伪语言表达了这一点，您可能需要对其进行调整以适用于特定语言（例如，在 C++ 中使用 uint32_t，在 Java 中使用 >>>）：
GCC10 和 clang 10.0 可以识别这种模式/习语，并在可用时将其编译为硬件 popcnt 或等效指令，为您提供两全其美的体验。（https://godbolt.org/z/qGdh1dvKK）
int numberOfSetBits(uint32_t i) { // Java: use int, and use >>> instead of >>. Or use Integer.bitCount() // C or C++: use uint32_t i = i - ((i >> 1) & 0x55555555); // add pairs of bits i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // quads i = (i + (i >> 4)) & 0x0F0F0F0F; // groups of 8 return (i * 0x01010101) >> 24; // horizontal sum of bytes }
对于 JavaScript：强制转换为整数;`
这具有所讨论的任何算法中最好的最坏情况行为，因此将有效地处理任何使用模式或您抛出的值。（它的性能不依赖于普通 CPU，其中包括乘法在内的所有整数运算都是恒定时间的。使用“简单”输入它不会变得更快，但它仍然相当不错。）
参考：
i = i - ((i >> 1) & 0x55555555);
第一步是屏蔽的优化版本，以隔离奇数/偶数位，将它们对齐并添加。这有效地在 2 位累加器中进行了 16 次单独的加法（SWAR = SIMD Within A Register）。喜欢(i & 0x55555555) + ((i>>1)& 0x55555555)。
(i & 0x55555555) + ((i>>1)& 0x55555555)
下一步取这些 16x 2 位累加器中的奇数/偶数 8 个并再次相加，产生 8x 4 位和。这次i - ...无法进行优化，因此它只是在移位之前/之后进行掩码。0x33...在为需要分别在寄存器中构造 32 位常量的 ISA 进行编译时，两次而不是在移位之前使用相同的常量0xccc...是一件好事。
i - ...
0x33...
0xccc...
最后的移位和加法步骤(i + (i >> 4)) & 0x0F0F0F0F扩展为 4 个 8 位累加器。 它在添加之后 而不是之前进行屏蔽，因为任何 4 位累加器中的最大值都是4，如果相应输入位的所有 4 位都已设置。4+4 = 8 仍然适合 4 位，因此半字节元素之间的进位在i + (i >> 4).
(i + (i >> 4)) & 0x0F0F0F0F
4
i + (i >> 4)
到目前为止，这只是使用 SWAR 技术和一些巧妙优化的相当普通的 SIMD。继续使用相同的模式再增加 2 个步骤可以扩大到 2x 16 位然后 1x 32 位计数。但是在具有快速硬件乘法的机器上，有一种更有效的方法：
一旦我们有足够少的“元素”， 一个带有魔法常数的乘法可以将所有元素相加到顶部元素 中。在这种情况下，字节元素。乘法是通过左移和加法完成的，所以 结果 的乘法是. x * 0x01010101``x + (x<<8) + (x<<16) + (x<<24) 我们的 8 位元素足够宽（并且保持足够小的计数），这不会产生进位 到 前 8 位。
x * 0x01010101``x + (x<<8) + (x<<16) + (x<<24)
64 位版本 可以使用 0x0101010101010101 乘法器在 64 位整数中处理 8x 8 位元素，并使用>>56. 所以它不需要任何额外的步骤，只是更广泛的常数。当硬件指令未启用时，这就是 GCC__builtin_popcountll在 x86 系统上的用途。popcnt如果您可以为此使用内置函数或内部函数，请这样做以使编译器有机会进行特定于目标的优化。
>>56
__builtin_popcountll
这种按位 SWAR 算法可以并行化以一次在多个向量元素中完成，而不是在单个整数寄存器中完成，以在具有 SIMD 但没有可用的 popcount 指令的 CPU 上加速。（例如，必须在任何 CPU 上运行的 x86-64 代码，而不仅仅是 Nehalem 或更高版本。）
但是，对 popcount 使用向量指令的最佳方法通常是使用变量混洗对每个字节并行执行 4 位的表查找。（4 位索引保存在向量寄存器中的 16 项表）。
在 Intel CPU 上，硬件 64 位 popcnt指令的性能可以比SSSE3PSHUFB位并行实现高出大约 2 倍，但前提是您的编译器可以做到恰到好处。否则 SSE可能会明显领先。较新的编译器版本知道 Intel 上的popcnt 错误依赖
PSHUFB
vpternlogd
