数字中设置的位数 [英] Number of bits set in a number
问题描述
以下神奇的公式给出了设置的数字位数(汉明权重).
The following the magical formula which gives the number of bits set in a number (Hamming weight).
/*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
任何人都可以向我解释其背后的原理吗?
Can anyone please explain me the rationale behind this?
推荐答案
这确实是非常聪明的代码,而且显然比简单的幼稚循环更难理解.
It's really quite clever code, and is obviously a lot more difficult to understand than a simple naive loop.
对于第一行,让我们只取一个四位的数量,并将其称为abcd
.该代码基本上是这样做的:
For the first line, let's just take a four-bit quantity, and call it abcd
. The code basically does this:
abcd - ((abcd >> 1) & 0101) = abcd - (0abc & 0101) = abcd - 0a0c
因此,在每个两位的组中,它减去高位的值.这对我们有什么好处?
So, in each group of two bits, it subtracts the value of the high bit. What does that net us?
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
.
So, that first line sets each consecutive group of two bits to the number of bits contained in the original value -- it counts the bits set in groups of two. Call the resulting four-bit quantity ABCD
.
下一行:
(ABCD & 0011) + ((ABCD>>2) & 0011) = 00CD + (AB & 0011) = 00CD + 00AB
因此,它采用两位的组并将对相加在一起.现在,每个四位组包含在输入的相应四位中设置的位数.
So, it takes the groups of two bits and adds pairs together. Now, each four-bit group contains the number of bits set in the corresponding four bits of the input.
在下一行中,v + (v >> 4) & 0xF0F0F0F
(被解析为(v + (v >> 4)) & 0xf0f0f0f
)执行相同的操作,将成对的四位组加在一起,以便每个八位组(字节)都包含对位的计数.相应的输入字节.现在我们有一个像0x0e0f0g0h
这样的数字.
In the next line, v + (v >> 4) & 0xF0F0F0F
(which is parsed as (v + (v >> 4)) & 0xf0f0f0f
) does the same, adding pairs of four-bit groups together so that each eight-bit group (byte) contains the bit-set count of the corresponding input byte. We now have a number like 0x0e0f0g0h
.
请注意,将任意位置的字节乘以0x01010101
会将该字节复制到最高有效字节(以及将一些副本保留在较低字节中).例如,0x00000g00 * 0x01010101 = 0x0g0g0g00
.因此,通过乘以0x0e0f0g0h
,我们将把e+f+g+h
保留在最上面的字节中.最后的>>24
会提取该字节并留下答案.
Note that multiplying a byte in any position by 0x01010101
will copy that byte up to the most-significant byte (as well as leaving some copies in lower bytes). For example, 0x00000g00 * 0x01010101 = 0x0g0g0g00
. So, by multiplying 0x0e0f0g0h
, we will leave e+f+g+h
in the topmost byte; the >>24
at the end extracts that byte and leaves you with the answer.
这篇关于数字中设置的位数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!