23

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

from: http://graphics.stanford.edu/~seander/bithacks.html

Can anyone please explain me the rationale behind this?

denfromufa
  • 5,610
  • 13
  • 81
  • 138
Anup Buchke
  • 5,210
  • 5
  • 22
  • 38
  • 9
    Good lord, there's no reason to memorize this kind of arcana except to show off (and anyone worth their salt should know the source anyway). – nneonneo Jan 28 '13 at 04:51
  • and of course, if you give such an answer in an interview, the next question would be "Explain". So no point memorizing, and frankly I wouldn't like seeing that in an interview anyway. – littleadv Jan 28 '13 at 04:55
  • Show us how you worked out your examples, step by step, one line at a time, and we'll help you find your error (in an addendum to the *question* please; **not** here in a comment). – WhozCraig Jan 28 '13 at 04:58
  • Anyone else find the 64-bit tag somewhat ironic for this question? – WhozCraig Jan 28 '13 at 05:01
  • 2
    I would recommend you write your own c routine to find the number of set bits. It can be done with some simple shifts and loops. If you can do that from scratch it's much better than memorizing something like the above, as others have alluded to. – Adam27X Jan 28 '13 at 05:03
  • @Adam27X I disagree. No I don't remember that stuff by heart (I read Warren's book on bittwiddling though and *can* derive the solution), but you don't have to. You only have to know where you can get the source. Compared to the looping code this is a whole lot more performant and anybody using bitsets hopefully does so for performance reasons. – Voo Jan 28 '13 at 05:10
  • @WhozCraig 64 bit tag is not ironic it is wrong. The formula works compute only for 32 bit integers (look at original homepage) – Eli Algranti Jan 28 '13 at 05:10
  • And if you understand it, it should be relatively trivial to extend to 64-bit quantities ;) – nneonneo Jan 28 '13 at 05:16
  • Seems patently obvious to me. (But then I have patent 6,516,330 on a similar algorithm.) – Hot Licks Jan 28 '13 at 05:21
  • The answer to this question has lots of useful references: http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer – Eli Algranti Jan 28 '13 at 05:21
  • @EliAlgranti I know its wrong; thus the irony. – WhozCraig Jan 28 '13 at 05:21
  • @HotLicks: And [here](http://www.google.com/patents?id=SRUPAAAAEBAJ&printsec=abstract) I thought you were joking... – nneonneo Jan 28 '13 at 06:34
  • @nneonneo - But everything I write here is true. And I never joke. – Hot Licks Jan 28 '13 at 12:51

2 Answers2

40

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

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)

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.

The next line:

(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.

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.

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.

nneonneo
  • 171,345
  • 36
  • 312
  • 383
-3

One liner solution in python for counting number of one's in a given binary number

[i for i in str(bin(n)) if i=="1"].count("1")

Kanishkar Rajeswari
  • 1