需要解释 - 在数设置的位数 [英] explanation required - Number of bits set in a number

问题描述

下面的神奇式赋予在许多设定的比特数。

the following the magical formula which gives the number of bits set in a number.

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

来自：
<一href=\"http://graphics.stanford.edu/~seander/bithacks.html\">http://graphics.stanford.edu/~seander/bithacks.html

谁能请解释我的理由背后?? ...它太复杂了......我试着锻炼一些examples..but不能数字出来...我不想记住这个公式为采访......想好好学学吧....请指导。

Can anyone please explain me the rationale behind this??...Its too complicated...I tried to workout some examples..but couldn't figure it out...I dont want to memorize this formula for the interview...want to learn it properly....Please guide..

推荐答案

这真的很聪明code和显然是很多更难理解比简单的天真循环。

It's really quite clever code, and is obviously a lot more difficult to understand than a simple naive loop.

有关的第一线，让我们只需要四位量，并将其命名为 ABCD 。在code基本上做到这一点：

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 。

下一行：

(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＆GT;＆GT; 4）及0xF0F0F0F （被解析为（V +（V＆GT;＆GT; 4））及0xf0f0f0f ）不一样，添加对的四比特组在一起，使每个8位组（字节）包含对应的输入字节的比特设定计数。我们现在有一个像 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 在最上面的字节;在＆GT;方式＆gt; 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屋！