Count the number of set bits in an integer [duplicate]

Question

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

I came across this question in an interview. I want to find the number of set bits in a given number in an optimized way.

Example:

If the given number is 7 then output should be 3 (since binary of 7 is 111 we have three 1s).

If the given number 8 then output should be 1 (since binary of 8 is 1000 we have one 1s).

We need to find the number of ones in an optimized way. Any suggestions?

Answer 1

Warren has a whole chapter about counting bits, including one about Conting 1-bits.

The problem can be solved in a divide and conquer manner, i.e. summing 32bits is solved as summing up 2 16bit numbers and so on. This means we just add the number of ones in two n bit Fields together into one 2n field.

Example:
10110010
01|10|00|01
0011|0001
00000100

The code for this looks something like this:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

We're using ((x >> 1) & 0x55555555) rather than (x & 0xAAAAAAAA) >> 1 only because we want to avoid generating two large constants in a register. If you look at it, you can see that the last and is quite useless and other ands can be omitted as well if there's no danger that the sum will carry over. So if we simplify the code, we end up with this:

int pop(unsigned x) {
   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0f0f0f0f;
   x = x + (x >> 8);
   x = x + (x >> 16);
   return x & 0x0000003f;
}

That'd be 21 instructions, branch free on a usual RISC machine. Depending on how many bits are set on average it may be faster or slower than the kerrigan loop - though probably also depends on the used CPU.