代表数字7的8位看起来像这样：
00000111
设置了三个位。
有什么算法可以确定32位整数中的设置位数？
这就是所谓的“汉明重量”，“弹出计数”或“横向添加”。
“最佳”算法实际上取决于您所使用的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);
这是所讨论的所有算法中最坏情况下的行为，因此可以有效地处理您使用的所有使用模式或值。
参考文献：
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 + 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系统上使用的功能。如果您可以为此使用内建函数或内在函数，请这样做使编译器有机会进行针对特定目标的优化。
这种逐位SWAR算法可以并行化，一次在多个矢量元素中完成，而不是在单个整数寄存器中完成，以提高具有SIMD但没有可用的popcount指令的CPU的速度。（例如，必须在任何CPU上运行的x86-64代码，而不仅仅是Nehalem或更高版本。）
但是，将向量指令用于popcount的最佳方法通常是使用可变混洗在每个字节并行的同时对4位进行表查找。（这4位索引了保存在向量寄存器中的16个条目表）。
在Intel CPU上，硬件64位popcnt指令的性能可以比SSSE3PSHUFB位并行实现高2倍左右，但前提是您的编译器正确地执行该指令。否则，上证所可能会明显领先。较新的编译器版本知道Intel上的popcnt错误依赖项 问题。
vpternlogd使得Harley-Seal非常出色。）本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句