Count the number of set bits in an integer

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?

Look at "Counting Bits Set" in [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive) — Ani, Mar 18 '11 at 21:22
Your question is not clear. What is a "number of bit field"? Number of individual 1-bits? Or the width from the first 1-bit to the last 1-bit? The examples you provided are chosen badly. They are ambiguous. For example, what is "number of bit field" for 10, which is `1010` in binary? Is it 2 or 3? — AnT stands with Russia, Mar 18 '11 at 21:41

Voo · Answer 1 · 2011-03-19T11:27:57.787

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.

score 2 · Answer 2 · answered Mar 18 '11 at 21:23

Conceptually this works:

int numones(int input) {
    int num = 0;
    do {
        num += input % 2;
        input = input / 2;
    } while (input > 0);
    return num;
 }

A more optimized way (from commenters link above):

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

score 2 · Answer 3 · answered Mar 18 '11 at 21:54

2

If you are using GCC, use the builtin function int __builtin_popcount (unsigned int x). On some machines, this will reduce to a single instruction.

answered Mar 18 '11 at 21:54

Null Set

5,374
24
37

but __builtin_popcount (unsigned int x) does not do this in a single instruction. It implicitly performs the methods described earlier. – Shamim Hafiz - MSFT May 03 '11 at 15:28
@gunner Sometimes it is a function, but sometimes it does replace it with a single instruction if the chip has a popcount instruction, at least according to the lore I have read. – Null Set May 03 '11 at 17:02

Count the number of set bits in an integer

3 Answers3

Linked

Related