数字中设置的位数
以下是一个神奇的公式，它给出了一个数字中设置的位数。
/*Code to Calculate count of set bits in a number*/ int c; int v = 7; v = v - ((v >> 1) & 0x55555555); // reuse input as temporary v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count printf(" Number of Bits is %d",c); /*-----------------------------------*/ 来自： http ： //graphics.stanford.edu/~seander/bithacks.html
有人可以解释一下这背后的理由吗？
这是非常聪明的代码，显然比简单的天真循环更难理解。
对于第一行，让我们只取四位数量，并将其称为abcd 。 代码基本上是这样的：
abcd - ((abcd >> 1) & 0101) = abcd - (0abc & 0101) = abcd - 0a0c
因此，在每组两位中，它减去高位的值。 这对我们有什么影响？
11 - 1 -> 10 (two bits set) 10 - 1 -> 01 (one bit set) 01 - 0 -> 01 (one bit set) 00 - 0 -> 00 (zero bits set)
因此，第一行将每个连续的两位组设置为原始值中包含的位数 – 它将以两个为一组的位进行计数。 调用生成的四位数量ABCD 。
下一行：
(ABCD & 0011) + ((ABCD>>2) & 0011) = 00CD + (AB & 0011) = 00CD + 00AB
因此，它需要两位组并将对加在一起。 现在，每个四位组包含在输入的相应四位中设置的位数。
在下一行中， v + (v >> 4) & 0xF0F0F0F （解析为(v + (v >> 4)) & 0xf0f0f0f ）相同，将四对组加在一起，使每个八位 – bit group（byte）包含相应输入字节的位设置计数。 我们现在有一个像0x0e0f0g0h的数字。
请注意，将任意位置的字节乘以0x01010101会将该字节复制到最高有效字节（以及在较低字节中保留一些副本）。 例如， 0x00000g00 * 0x01010101 = 0x0g0g0g00 。 因此，通过乘以0x0e0f0g0h ，我们将在最顶层的字节中留下e+f+g+h ; 最后的>>24提取该字节并给你答案。