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

Question

int SWAR(unsigned int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

我已经看到这个代码计算的位数等于132位整数,我注意到它的性能优于__builtin_popcount但我无法理解它的工作方式.

有人可以详细解释这段代码是如何工作的吗？

Answer 1

好的,让我们逐行完成代码:

第1行:

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

首先,常量的意义0x55555555在于,使用Java/GCC样式二进制文字表示法编写),

0x55555555 = 0b01010101010101010101010101010101

也就是说,它的所有奇数位(将最低位计为位1 =奇数)都是1,并且所有偶数位都是0.

因此,表达式((i >> 1) & 0x55555555)将i右位移位1,然后将所有偶数位设置为零.(同样地,我们可能已经第一次设置的所有奇数位i到零& 0xAAAAAAAA和再移位一位,结果右)为方便起见,我们称之为中间值j.

当我们j从原始中减去这个时会发生什么i？那么,让我们看看如果i只有两位会发生什么:

    i           j         i - 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数值永远不会比那些数值大i,所以减法永远不会从第三位借用i:因此,最低两位i也不会影响第三位或更高位i - j.

实际上,通过重复相同的参数,我们可以看到该行上的计算实际上将上面的表应用于并行的16个两位块中的每一个.也就是说,在执行这条线之后,新的价值的最低两位现在将包含数在原来的值对应的位中设置位,等会下两个位,依此类推.i ii

第2行:

i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

与第一行相比,这一行非常简单.首先,请注意

0x33333333 = 0b00110011001100110011001100110011

因此,i & 0x33333333取上面计算的两位计数并丢弃它们中的每一位,而在右移两位后(i >> 2) & 0x33333333则相同.然后我们将结果一起添加.i

因此,实际上,这行做的是采取两个最低的bitcounts和原始输入,计算上一行的第二低两位,并加入他们一起打的最低的比特计数4的位输入.而且,它同样为输入的所有 8个四位块(=十六进制数字)并行执行此操作.

第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 << 8术语加上下一个低字节的值
• 由于k << 16术语加上第二个低字节的值
• 由于该k << 24术语,第四个和最低字节的值.

(一般情况下,也可能有较低字节的进位,但由于我们知道每个字节的值最多为8,因此我们知道加法永远不会溢出并创建进位.)

也就是说,最高字节的k * 0x01010101结尾是输入的所有字节的bitcounts的总和,即32位输入数的总bitcount.然后,最终>> 24只是将该值从最高字节向下移动到最低字节.

PS.只需更改0x01010101to 0x0101010101010101和>> 24to ,就可以轻松地将此代码扩展为64位整数>> 56.实际上,相同的方法甚至适用于128位整数; 然而,256位将需要添加一个额外的移位/添加/屏蔽步骤,因为数字256不再完全适合8位字节.

Answer 2

我更喜欢这个,它更容易理解.

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);