这个计算32位整数中设置位数的算法是如何工作的？
这个计算32位整数中设置位数的算法是如何工作的？
提问于 2014-02-28 06:16:37
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更好，但我不能理解它的工作方式。
有没有人能详细解释一下这段代码是如何工作的？
回答 2
Stack Overflow用户
发布于 2015-04-14 15:53:21
我更喜欢这个，它更容易理解。
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);Stack Overflow用户
发布于 2017-02-02 00:28:41
这是对Ilamari's answer的评论。我把它作为一个答案，因为格式问题：
第1行：
i = i - ((i >> 1) & 0x55555555); // (1)此行是从此easier to understand line派生的
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)我们想证明(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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22081738
复制相关文章
相似问题