Count the number of set bits in an integer
Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?
Hi ,
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?
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, ie 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.
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
}
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.
上一篇: 计数数字中的位
下一篇: 计数整数中的设定位数