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

第1行：

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

首先，常量的意义0x55555555在于，使用Java /
GCC样式的二进制文字符号）编写了该常量，

0x55555555 = 0b01010101010101010101010101010101

即，其所有奇数位（将最低位计为bit 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个2位块中的 每个
块。也就是说，在执行这条线之后，新的价值的最低两位将现在包含 数 在原始值的对应位中设置位，等会下两个位，依此类推。i i i

第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位字节组成的32位数字，每个字节保存原始输入的那个字节中的1位数字。（我们叫这些字节A，B，C和D。）所以，当我们乘这个值（我们称之为会发生什么k的）0x01010101？

好吧，由于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仅将这个值从最高字节降低到最低字节。

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