如何计算32位整数中的设置位数？

一尘不染

如何计算32位整数中的设置位数？

algorithm

代表数字7的8位看起来像这样：

00000111

设置了三个位。

确定32位整数中的置位位数的算法是什么？

阅读 316

2020-07-28

共1个答案

一尘不染

这就是所谓的“ 汉明重量 ”，“弹出计数”或“横向添加”。

“最佳”算法实际上取决于您所使用的CPU以及您的使用模式。

一些CPU具有单个内置指令来执行此操作，而另一些CPU具有作用于位向量的并行指令。并行指令（如x86一样popcnt，在受支持的CPU上）几乎可以肯定是最快的。其他一些体系结构可能有一条慢指令，该指令通过微编码循环实现，该循环每个周期测试一位（
需要引用 ）。

如果您的CPU具有较大的缓存，并且/或者您在紧密的循环中执行了许多此类指令，那么预填充的表查找方法可能会非常快。但是，由于“高速缓存未命中”的代价，它可能会遭受损失，在这种情况下，CPU必须从主内存中获取某些表。（分别查找每个字节以使表较小。）

如果您知道字节将大部分为0或大多数为1，那么对于这些情况，有非常有效的算法。

我相信以下是一种非常好的通用算法，称为“并行”或“可变精度SWAR算法”。我已经用类似C的伪语言表示了这一点，您可能需要对其进行调整以使其适用于特定语言（例如，对于C++使用uint32_t，而在Java中使用>>>）：

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and 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;
}

对于JavaScript：强制转换为，|0以提高性能：将第一行更改为i = (i|0) - ((i >> 1) & 0x55555555);

在所讨论的所有算法中，这都是最坏的情况，因此可以有效地处理您使用的所有使用模式或值。

该SWAR bithack的工作方式：

i = i - ((i >> 1) & 0x55555555);

第一步是屏蔽的优化版本，以隔离奇数/偶数位，进行移位以将它们对齐并添加。这样可以有效地在2位累加器中进行16个独立的加法运算（SWAR
= A寄存器内的SIMD）。像(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步将使用那些16x 2位累加器的奇/偶八，然后再次相加，产生8x 4位和。这次i - ...无法进行优化，因此仅在移位之前/之后进行屏蔽。对于需要在寄存器中分别构造32位常量的ISA进行编译时，0x33...两次使用相同的常量而不是0xccc...在移位之前使用都是好事。

最后的移位加法步骤(i + (i >> 4)) & 0x0F0F0F0F扩展到4个8位累加器。由于在任何4位累加器中的最大值都设置为，因此它将在
加法之后而不是之前进行掩码4。4 + 4 = 8仍然适合4位，因此在中不能在半字节元素之间进位i + (i >> 4)。

到目前为止，这只是使用SWAR技术和一些巧妙优化的相当普通的SIMD。以相同的模式继续执行另外2个步骤，可以扩大到2x 16位然后1x
32位计数。但是在硬件快速乘法的机器上，有一种更有效的方法：

一旦我们的“元素”不足， 乘以一个魔术常数就可以将所有元素求和成顶层元素 。在这种情况下，字节元素。乘法是通过左移和加法完成的，因此 的x * 0x01010101结果相乘x + (x<<8) + (x<<16) + (x<<24)。
我们的8位元素足够宽（并且保持足够小的数量），因此不会产生高8位进位。

其64位版本 可以使用0x0101010101101010101乘法器以64位整数形式处理8x
8位元素，并使用提取高字节>>56。因此，它不需要采取任何额外的步骤，只需使用更宽的常量即可。__builtin_popcountll当popcnt未启用硬件指令时，这就是GCC
在x86系统上使用的功能。如果您可以为此使用内建函数或内在函数，请这样做使编译器有机会进行针对特定目标的优化。

具有完整的SIMD，可用于更宽的向量（例如，对整个数组进行计数）

这种逐位SWAR算法可以并行化以一次在多个向量元素中完成，而不是在单个整数寄存器中完成，以提高具有SIMD但没有可用的popcount指令的CPU的速度。（例如，必须在任何CPU上运行的x86-64代码，而不仅仅是Nehalem或更高版本。）

但是，将向量指令用于popcount的最佳方法通常是使用可变混洗在每个字节并行的同时对4位进行表查找。（这4位索引了保存在向量寄存器中的16个条目表）。

在Intel CPU上，硬件64位popcnt指令的性能可以比SSSE3
PSHUFB位并行实现高大约2倍，但前提是您的编译器正确地执行该指令。否则，上证所可能会明显领先。较新的编译器版本知道Intel上的popcnt错误依赖项
问题。

参考文献：

2020-07-28