23 
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但我无法理解它的工作方式。

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

4

4 回答 4

40

好的，让我们逐行浏览代码：

第 1 行：

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

首先，常量的意义0x55555555在于，使用 Java/GCC 风格的二进制文字表示法编写），

0x55555555 = 0b01010101010101010101010101010101

也就是说，它的所有奇数位（将最低位计算为位 1 = 奇数）是1，所有偶数位都是0。

因此，该表达式((i >> 1) & 0x55555555)将i右移一位，然后将所有偶数位设置为零。（等效地，我们可以先将 的所有奇数位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

因此，实际上，这一行所做的是将在前一行计算的原始输入的最低两位和倒数第二位的位计数，并将它们加在一起以给出最低四位的位计数输入。而且，它对输入的所有8 个四位块（= 十六进制数字）并行执行此操作。

第 3 行：

return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;

好的，这是怎么回事？

好吧，首先，(i + (i >> 4)) & 0x0F0F0F0F它与上一行完全相同，只是它将相邻的四位位计数加在一起以给出输入的每个八位块（即字节）的位计数。（在这里，与上一行不同，我们可以避免移动&外部加法，因为我们知道 8 位的位数永远不会超过 8，因此可以容纳在 4 位内而不会溢出。）

现在我们有一个由四个 8 位字节组成的 32 位数字，每个字节保存原始输入的那个字节中的 1 位的数量。（我们称这些字节为 、 和A。B）那么当我们将这个值（我们称它为）乘以 时会发生什么？CDk0x01010101

好吧，因为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最终是输入的所有字节的位数之和，即32位输入数的总位数。然后最后>> 24简单地将这个值从最高字节向下移动到最低字节。

附言。0x01010101只需更改to0x0101010101010101和>> 24to即可轻松将此代码扩展为 64 位整数>> 56。事实上，同样的方法甚至适用于 128 位整数；但是，256 位需要添加一个额外的移位/添加/掩码步骤，因为数字 256 不再完全适合 8 位字节。

于 2014-02-28T00:54:41.843 回答
15

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

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);
于 2015-04-14T07:53:20.503 回答
4

这是对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)

我们想证明（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
于 2017-02-01T16:28:40.603 回答
0

这是对yeer的回答的解释：

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 行作为我解释的基础。

i = (i & 0x55555555) + ((i >> 1) & 0x55555555)

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

i = (i & mask) + ((i >> 1) & mask)
  = A1         + A2

首先，i不要将其视为 32 位，而是将其视为 16 组的数组，每组 2 位。A1是大小为 16 的计数数组，每组包含1s 中相应组最右边位的计数i：

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

同样，A2是“计数”中每个组的最左边的位i。请注意，我可以重写A2 = (i >> 1) & mask为A2 = (i & mask2) >> 1：

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 + A2将A1数组和A2数组的计数相加，得到一个 16 组的数组，每组现在包含每组中的位数。

移动到 B 行，我们可以将该行重命名如下：

i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
  = (i & mask)       + ((i >> 2) & mask)
  = B1               + B2

B1 + B2遵循与以前相同的“形式” A1 + A2。不再i将其视为 16 组 2 位，而是视为 8 组 4 位。所以和之前类似，B1 + B2将 和 的个数B1相加B2，其中s 在组右侧的B1计数， 是组左侧的计数。因此是每组中的位数。1B2B1 + B2

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

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;
}
于 2022-01-17T16:52:58.157 回答