首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >这个计算32位整数中设置位数的算法是如何工作的?

这个计算32位整数中设置位数的算法是如何工作的?
EN

Stack Overflow用户
提问于 2014-02-28 06:16:37
回答 3查看 6.2K关注 0票数 23
代码语言:javascript
复制
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更好,但我不能理解它的工作方式。

有没有人能详细解释一下这段代码是如何工作的?

EN

回答 3

Stack Overflow用户

发布于 2015-04-14 15:53:21

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

代码语言:javascript
复制
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);
票数 14
EN

Stack Overflow用户

发布于 2017-02-02 00:28:41

这是对Ilamari's answer的评论。我把它作为一个答案,因为格式问题:

第1行:

代码语言:javascript
复制
i = i - ((i >> 1) & 0x55555555);  // (1)

此行是从此easier to understand line派生的

代码语言:javascript
复制
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);  // (2)

如果我们调用

代码语言:javascript
复制
i = input value
j0 = i & 0x55555555
j1 = (i >> 1) & 0x55555555
k = output value

我们可以重写(1)和(2)以使解释更清楚:

代码语言:javascript
复制
k =  i - j1; // (3)
k = j0 + j1; // (4)

我们想证明(3)可以由(4)导出。

i可以写入为其偶数位和奇数位的相加(将最低位计数为位1=奇数):

代码语言:javascript
复制
i = iodd + ieven =
  = (i & 0x55555555) + (i & 0xAAAAAAAA) =
  = (i & modd) + (i & meven)

由于meven掩码清除了i的最后一位,因此可以这样写最后一个相等:

代码语言:javascript
复制
i = (i & modd) + ((i >> 1) & modd) << 1 =
  = j0 + 2*j1

这就是:

代码语言:javascript
复制
j0 = i - 2*j1    (5)

最后,将(5)替换为(4),我们得到(3):

代码语言:javascript
复制
k = j0 + j1 = i - 2*j1 + j1 = i - j1
票数 3
EN

Stack Overflow用户

发布于 2022-01-17 16:52:58

这是对yeer's answer的解释

代码语言:javascript
复制
int SWAR(unsigned int i) {
  i = (i & 0x55555555) + ((i >> 1) & 0x55555555);  // A
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // B
  i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);  // C
  i = (i & 0x00ff00ff) + ((i >> 8) & 0x00ff00ff);  // D
  i = (i & 0x0000ffff) + ((i >> 16) &0x0000ffff);  // E
  return i;
}

让我们使用A行作为我的解释的基础。

代码语言:javascript
复制
i = (i & 0x55555555) + ((i >> 1) & 0x55555555)

让我们将上面的表达式重命名如下:

代码语言:javascript
复制
i = (i & mask) + ((i >> 1) & mask)
  = A1         + A2 

首先,不要把i看作32位,而是一个由16组组成的数组,每组2位。A1是大小为16的计数数组,每组包含i中相应组最右边的1的计数

代码语言:javascript
复制
i        = yx yx yx yx yx yx yx yx yx yx yx yx yx yx yx yx
mask     = 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
i & mask = 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x

类似地,A2i中的每个组“计数”最左边的位。请注意,我可以将A2 = (i >> 1) & mask重写为A2 = (i & mask2) >> 1

代码语言:javascript
复制
i                = yx yx yx yx yx yx yx yx yx yx yx yx yx yx yx yx
mask2            = 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
(i & mask2)      = y0 y0 y0 y0 y0 y0 y0 y0 y0 y0 y0 y0 y0 y0 y0 y0
(i & mask2) >> 1 = 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y 0y

(请注意,mask2 = 0xaaaaaaaa__)

因此,A1 + A2A1数组和A2数组的计数相加,得到16个组的数组,每个组现在包含每个组中的位数。

移到行B,我们可以重命名该行,如下所示:

代码语言:javascript
复制
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
  = (i & mask)       + ((i >> 2) & mask)
  = B1               + B2

B1 + B2遵循与之前的A1 + A2相同的“形式”。i不再是16个2位的组,而是8个4位的组。因此,与前面类似,B1 + B2B1B2的计数相加,其中B1是组右侧的1计数,B2是组左侧的计数。因此,B1 + B2是每个组中的比特计数。

C到E行现在变得更容易理解了:

代码语言:javascript
复制
int SWAR(unsigned int i) {
  // A: 16 groups of 2 bits, each group contains number of 1s in that group.
  i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
  // B: 8 groups of 4 bits, each group contains number of 1s in that group.
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  // C: 4 groups of 8 bits, each group contains number of 1s in that group.
  i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
  // D: 2 groups of 16 bits, each group contains number of 1s in that group.
  i = (i & 0x00ff00ff) + ((i >> 8) & 0x00ff00ff);
  // E: 1 group of 32 bits, containing the number of 1s in that group.
  i = (i & 0x0000ffff) + ((i >> 16) &0x0000ffff);

  return i;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22081738

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档