c++ - 该算法如何计算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样式binary literal notation编写的,
0x55555555 = 0b01010101010101010101010101010101

也就是说,其所有奇数位(将最低位计数为位1=奇数)都是1,所有偶数位都是0
因此表达式将((i >> 1) & 0x55555555)的位右移1,然后将所有偶数位设置为零。(同样地,我们可以先用i将所有奇数位设置为零,然后将结果右移一位。)为了方便起见,我们将此中间值称为i
当我们从原始值中减去这个值时会发生什么?好吧,让我们看看如果& 0xAAAAAAAA只有两个位会发生什么:
    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

嘿!我们已经计算了两位数字的位数!
好的,但是如果j设置了两个以上的位呢?实际上,很容易检查上表是否仍然给出了j的最低两位,第三位和第四位,第五位和第六位,等等。特别地:
尽管存在i,但i的最低两位不受i的第三位或更高位的影响,因为它们将被i - j屏蔽掉;并且
由于>> 1的最低两位的数值永远不会大于i - j的数值,因此,从i的第三位中减去的数值永远不会借用。j的最低两位也不会影响& 0x55555555的第三位或更高位。
事实上,通过重复相同的参数,我们可以看到这行的计算实际上将上表应用于并行的j中16个两位块中的每一个。也就是说,在执行此行之后,i的新值的最低两位现在将包含在初始值中相应位之间设置的位数,接下来的两位也是如此,依此类推。
第2行:
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

与第一行相比,这一行相当简单。首先,注意
0x33333333 = 0b00110011001100110011001100110011

因此,i接受上面计算的两个位计数并每秒丢弃其中一个,而将i右移两位后,i - j也会这样做。然后我们把结果加在一起。
因此,实际上,这一行所做的是取原始输入的最低两位和第二个最低两位的比特数,在前一行上计算,然后将它们相加,得到输入的最低四位的比特数。同样,它对输入的所有8个四位块(=hex位)并行执行此操作。
第3行:
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;

好吧,这是怎么回事?
首先,i与前一行完全相同,只是它将相邻的四位比特计数相加,得到输入的每个八位块(即字节)的比特计数。(这里,与前一行不同,我们可以将i移到加法之外,因为我们知道8位比特计数永远不能超过8,因此可以在不溢出的情况下放入4位。)
现在我们有一个32位的数字,由四个8位字节组成,每个字节在原始输入的那个字节中保持1位的数字。(让我们称这些字节为ii & 0x33333333(i >> 2) & 0x33333333i)那么当我们将这个值(让我们称之为(i + (i >> 4)) & 0x0F0F0F0F)乘以&时会发生什么?
好吧,从A开始,我们有:
k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k

因此,结果的最高字节最终是:
其原始值,由于B项,加上
下一个较低字节的值,由于C项,加上
由于D项,第二个较低字节的值,加上
由于k项,第四个和最低字节的值。
(一般来说,也可以从较低的字节进行进位,但由于我们知道每个字节的值最多为8,所以我们知道加法永远不会溢出并创建进位。)
也就是说,0x01010101的最高字节最终是输入所有字节的比特数之和,即32位输入数的总比特数。最后一个0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1简单地将这个值从最高字节移到最低字节。
这些代码可以很容易地扩展到64位整数,只需将k更改为k << 8k << 16更改为k << 24。实际上,同样的方法甚至适用于128位整数;256位需要添加一个额外的移位/添加/屏蔽步骤,但是,由于256号不再完全适合8位字节。

本文翻译自 https://stackoverflow.com/questions/22081738/

网站遵循 CC BY-SA 4.0 协议,转载或引用请注明出处。

标签 c++ c algorithm hammingweight


相关文章:

c++ - 可观察的容器

c++ - 没有匹配运算符==的2D向量,枚举和指针

c - 编译器在编译时跳过语句?

algorithm - 最佳和最差情况-时间复杂度

algorithm - KdTree节点删除

algorithm - 查找矩阵的立方体的时间复杂度是多少?

c++ - libmorph API文档[关闭]

c++ - 如何在C ++中仅读取文本文件中的数字

java - 有什么办法可以在任何更新中将通知从Flash Air卡发送到Android App?

c - 在C中使用:运算符