c++ - 此代码如何计算 1 位的数量？

Question

我找到了以下代码来计算给定整数的二进制表示形式中 1 位 的数量。谁能解释它是如何工作的？以及如何为此类任务选择位掩码？谢谢。

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 作为计算源和内存。首先，考虑一下位掩码是什么:

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

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

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

如果我们将这两个加在一起，我们就得到每两个位对的位计数。此结果最多为 0x10，因为每次添加时掩码仅设置一位。

现在，我们使用 0x33 掩码，记住每个连续的 2 位包含第一个操作的结果。使用此掩码，我们屏蔽掉连续的 4 位并将它们相加。此结果最多为 0x100。这对其他掩码继续进行，直到我们在 x 中得到结果。

在纸上试一下，几步之后就很清楚了。