该算法如何计算32位整数中的设置位数？
int SWAR(unsigned int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } 我已经看到这个代码计算32位整数中的位数等于1 ，我注意到它的性能优于__builtin_popcount但我无法理解它的工作方式。
有人可以详细解释这段代码的工作原理吗？
好的，让我们逐行完成代码：
第1行：
i = i - ((i >> 1) & 0x55555555);
首先，常量0x55555555的意义是，使用Java / GCC样式二进制文字表示法编写），
0x55555555 = 0b01010101010101010101010101010101
也就是说，其所有奇数位（将最低位计为位1 =奇数）为1 ，并且所有偶数位为0 。
表达式((i >> 1) & 0x55555555)因此将i的位右移1，然后将所有偶数位设置为零。 （等效地，我们可以先用& 0xAAAAAAAA将i所有奇数位设置为零， 然后将结果右移一位。）为方便起见，让我们调用这个中间值j 。
当我们从原始i减去这个j时会发生什么？ 好吧，让我们看看如果i只有两位会发生什么：
iji - j ---------------------------------- 0 = 0b00 0 = 0b00 0 = 0b00 1 = 0b01 0 = 0b00 1 = 0b01 2 = 0b10 1 = 0b01 1 = 0b01 3 = 0b11 1 = 0b01 2 = 0b10
嘿! 我们设法计算了两位数的位数！
好的，但如果i设置了两位以上怎么办？ 实际上，很容易检查i - j的最低两位仍将由上表给出， 第三和第四位 ，以及第五和第六位也是如此。 特别是：
-
尽管
>> 1，i - j的最低两位不受i - j的第三或更高位的影响，因为它们将被& 0x55555555从j屏蔽掉; 和 -
因为
j的最低两位永远不会具有比i更大的数值，所以减法永远不会从i的第三位借用：因此，i的最低两位也不能影响i的第三位或更高位。i - j。
实际上，通过重复相同的参数，我们可以看到该行的计算实际上将上面的表应用于并行的 i 中的16个两位块中的每一个 。 也就是说，在执行该行之后， i的新值的最低两位现在将包含i的原始值中的相应位中设置的位数，接下来的两位也是如此，依此类推。
第2行：
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
与第一行相比，这一行非常简单。 首先，请注意
0x33333333 = 0b00110011001100110011001100110011
因此， i & 0x33333333采用上面计算的两位计数并抛弃它们中的每一位，而(i >> 2) & 0x33333333 在将i右移两位后执行相同操作。 然后我们将结果一起添加。
因此，实际上，这一行所做的是获取原始输入的最低两位和第二低两位的bitcounts，在前一行上计算，并将它们加在一起以给出最低四位的bitcount。输入。 并且，它再次并行地对输入的所有 8个四位块（=hex数字）执行此操作。
第3行：
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
好的，这里发生了什么？
好吧，首先， (i + (i >> 4)) & 0x0F0F0F0F与前一行完全相同，只是它将相邻的四位比特加在一起以给出每个八比特块的比特 （即字节） ）输入。 （这里，与上一行不同，我们可以通过移动&移出加法，因为我们知道8位bitcount永远不会超过8，因此它将适合四位而不会溢出。）
现在我们有一个由4个8位字节组成的32位数字，每个字节保存原始输入字节中的1位数。 （让我们称这些字节为A ， B ， C和D ）那么当我们将这个值（让我们称之为k ）乘以0x01010101什么？
好吧，因为0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1 ，我们有：
k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k
因此，结果的最高字节最终为以下总和：
- 它的原始值，由于
k项，加上 - 由于
k << 8term，加上下一个低字节的值 - 由于
k << 16项加上，第二个低字节的值 - 由于
k << 24项，第四个和最低字节的值。
（一般情况下，也可能存在较低字节的数据，但由于我们知道每个字节的值最多为8，因此我们知道添加将永远不会溢出并创建进位。）
也就是说， k * 0x01010101的最高字节最终是输入的所有字节的bitcounts的总和，即32位输入数的总bitcount。 最后>> 24然后简单地将该值从最高字节向下移动到最低字节。
PS。 只需将0x01010101更改为0x0101010101010101 ，将>> 24更改为>> 56即可轻松将此代码扩展为64位整数。 实际上，相同的方法甚至适用于128位整数; 然而，256位将需要添加一个额外的移位/添加/屏蔽步骤，因为数字256不再完全适合8位字节。
我更喜欢这个，它更容易理解。
x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f); x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff); x = (x & 0x0000ffff) + ((x >> 16) &0x0000ffff);
这是对Ilamari答案的评论。 我把它作为答案，因为格式问题：
第1行：
i = i - ((i >> 1) & 0x55555555); // (1)
这一行源于这个更容易理解的界限 ：
i = (i & 0x55555555) + ((i >> 1) & 0x55555555); // (2)
如果我们打电话
i = input value j0 = i & 0x55555555 j1 = (i >> 1) & 0x55555555 k = output value
我们可以重写（1）和（2）以使解释更清楚：
k = i - j1; // (3) k = j0 + j1; // (4)
我们想certificate（3）可以从（4）推导出来。
i可以写为偶数和奇数位的加法（将最低位计为位1 =奇数）：
i = iodd + ieven = = (i & 0x55555555) + (i & 0xAAAAAAAA) = = (i & modd) + (i & meven)
由于meven掩码清除了i的最后一位，所以最后的相等可以这样写：
i = (i & modd) + ((i >> 1) & modd) << 1 = = j0 + 2*j1
那是：
j0 = i - 2*j1 (5)
最后，将（5）替换为（4）我们实现（3）：
k = j0 + j1 = i - 2*j1 + j1 = i - j1