这段代码如何计算1位数？

Question

我找到以下代码来计算1-bits给定整数的二进制表示的数量.谁能解释它是如何工作的？如何为这样的任务选择位掩码？谢谢.

int count_one(int x)
{
    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));
    return x;
}

Answer 1

该算法x既用作计算源,又用作存储器.首先,考虑一下bitmasks是什么:

0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111

让我们看一个8位的例子:a = 01101010

a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101 

如果我们将这两者加在一起,我们得到每两位对的位数.这个结果最多0x10,因为掩码只为每次加法设置了一个位.

现在,我们使用0x33掩码,记住每个连续的2位包含第一次操作的结果.使用此掩码,我们屏蔽掉连续的4位并添加它们.这个结果最多0x100.这与其他面具一样,直到我们得到结果x.

在纸上试一下,经过几个步骤就可以很清楚了.

Answer 2

这是一种分而治之的方法。请注意，第一行将为您提供后续对的总和，接下来为后续四倍的总和，...最后是位数。

示例（16位，因此请考虑没有最后一行的代码）

1011001111000110

在第一行中，我们将&偶数位和奇数位移位了一个。然后我们添加。

对于偶数位：

num:  10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res:  00 01 00 01 01 00 01 00

对于奇数位：

num>>1: 01 01 10 01 11 10 00 11
mask:   01 01 01 01 01 01 01 01
res:    01 01 00 01 01 00 00 01

我们将这些结果相加并在后续对中求和

01 10 00 10 10 00 01 01

我们对以下蒙版和相应的移位重复相同的操作

2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111

我们得到：

2nd: 0011 0010 0010 0010  // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100  // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001  // 9 bits in total