数字中设置的位数

Question

以下是一个神奇的公式,它给出了一个数字中设置的位数(汉明重量).

/*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

有谁能解释一下这背后的理由？

Answer 1

这是非常聪明的代码,显然比简单的天真循环更难理解.

对于第一行,我们只需要四位数量,然后调用它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)执行相同操作,将四对组对添加到一起,以便每个八位组(字节)包含相应输入字节的位设置计数.我们现在有一些像0x0e0f0g0h.

请注意,在任何位置乘以一个字节0x01010101都会将该字节复制到最高有效字节(以及在较低字节中保留一些副本).例如,0x00000g00 * 0x01010101 = 0x0g0g0g00.所以,通过乘法0x0e0f0g0h,我们将留e+f+g+h在最顶层的字节; 将>>24在年底提取该字节,并让你的答复.