"Count the number of set bits in a 32-bit integer"的意思是“统计32位整数中设置为1的位数”。

39 浏览
0 Comments

"Count the number of set bits in a 32-bit integer"的意思是“统计32位整数中设置为1的位数”。

用8位二进制表示数字7，看起来像这样：

00000111

三个位被设置为1。

如何确定32位整数中设置的位数的算法？

admin 更改状态以发布 2023年5月22日
0

2 答案

0 Comments

输出内容缺失

0
0 Comments

这被称为“汉明重量”，“popcount”或“侧向加法”。

有些 CPU 有单个内置指令可以执行此操作，而其他 CPU 则有并行指令可以操作位向量。诸如 x86 的popcnt（如果支持），将几乎肯定是单个整数最快的。其他一些架构可能会使用一个慢速指令，该指令通过微编码循环每周期测试一个 bit（需要引证 - 如果硬件 popcount 存在，通常是很快的）。

“最佳”算法实际上取决于你所在的 CPU 和你的使用模式。

你的编译器可能知道如何为你编译的特定 CPU 执行某些好的操作，例如C++20 的 std::popcount()或 C++ 的std::bitset<32>::count()，作为访问 builtin/intrinsic 函数的便携式方式（请参见这个问题的另一个答案）。但是，针对没有硬件 popcnt 的目标 CPU，你的编译器选择的回退可能不适合你的用例。或者你的语言（例如 C）可能不会公开任何可便携使用特定 CPU 的 popcount 的函数。

不需要（或无法受益于）任何硬件支持的便携式算法

如果你的 CPU 有一个大缓存并且你在一个紧密循环中执行大量这些操作，则预填充表查找方法可能非常快。但是，它可能会受到“缓存未命中”的影响，其中 CPU 必须从主存中获取某个表中的一些数据。（单独查找每个字节可以使表较小。）如果你要对一系列连续的数字进行 popcount，只有低字节会针对 256 个数字组发生变化，使其非常好。

如果你知道你的字节将主要为 0 或 1，则有针对这些场景的有效算法，例如在循环中使用位 hack 清除最低设置，直到其变为零。

我相信一个非常好的通用算法是以下算法，称为“并行”或“可变精度 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代码：转换成整数会提升性能，使用|0：将第一行改为i = (i|0) - ((i >> 1) & 0x55555555);

该算法讨论中具有最佳平均复杂度，可以有效处理各种用法模式和值。在常规CPU上，所有整数操作包括乘法的时间都是恒定的，它的性能并不基于数据，因此无论输入多么“简单”，其性能都不会变得更快，但仍然非常不错。

参考文献：

这个SWAR二进制技巧如何工作：

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

第一步是一个优化版的掩码操作，用于隔离奇/偶比特位，并将它们移位对齐，然后相加。这实际上在2比特的累加器中完成了16次单独的加法（SWAR = 在寄存器内的SIMD），类似于(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步是将这16个2比特的累加器中的奇/偶八个再次相加，产生8个4比特的和。这一次不可能使用i-...优化，因此只是在移位之前/之后执行掩码操作。两次使用相同的0x33...常量而不是0xccc...常量是一个好事情，因为在编译ISA需要单独在寄存器中构造32位常量时，可以省去不必要的操作。

(i + (i >> 4)) & 0x0F0F0F0F的最后一步将其扩大为4个8比特的累加器。在加法之后而不是之前执行掩码操作，因为对应输入比特的任何4个比特累加器中的最大值都是4，即所有4比特都设置。4 + 4 = 8仍适用于4比特，所以在i + (i >> 4)中，零件之间的进位是不可能的。

到目前为止，这只是使用SWAR技术进行相当正常的SIMD技术，并具有一些巧妙的优化。继续使用相同的模式进行两个步骤，可以将其扩大为2个16比特，然后是1个32比特的统计。但是，在具有快速硬件乘法的计算机上，有更高效的方法：

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

64位版本可以使用0x0101010101010101乘数在64位整数中做8x 8位元素，并使用>>56提取高字节。因此，它不需要任何额外的步骤，只需要更宽的常量。这是GCC在x86系统上使用__builtin_popcountll时的做法，当硬件popcnt指令未启用时。如果您可以使用内置函数或内部函数，则应这样做，以使编译器有机会执行特定于目标的优化。

对于更宽的向量完全使用SIMD（例如统计整个数组）

这个按位Swar算法可以并行化为同时在多个向量元素中进行，而不是在单个整数寄存器中进行，对于在拥有SIMD但无可用popcount指令的CPU上进行加速非常有用（例如要在任何CPU上运行的x86-64代码，而不仅仅是在Nehalem或更高版本上）。

然而，使用矢量指令进行popcount的最佳方法通常是使用可变的Shuffle来对每个字节的4位进行表查找以进行并行处理。 （这4位将索引存储在矢量寄存器中的16个条目表中）。

在英特尔CPU上，硬件64位popcnt指令可以比SSSE3 PSHUFB位并行实现快大约2倍，但只有如果您的编译器做得恰到好处才有可能。否则，SSE可能会明显领先。最新版本的编译器已经意识到了在英特尔上的popcnt false dependency问题。

0