Count the number of bits set using only bitwise operations [duplicate]
Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?
Using only ! ~ & ^ | + << >> operators, I need to count the number of bits set in a 32 bit integer while only accessing directly 8 bits. So only 0xaa not 0xaaaa
Ex. 0x07 = 3 and 0x05 = 2
I also can only use a max of 40 operators.
Right now my solution uses 90 and is:
int countBitsSet(int x)
{
int count = 0;
int mask = 0x01 // 00000001
count = (x & mask);
count += (x >> 1) & mask;
count += (x >> 2) & mask;
.
.
.
count += (x >> 31) & mask;
return count;
}
Does anyone know of a way to reduce this step by half? I was thinking of finding a way to do it in parallel or something and count 4 bits at once but I cant figure out how. Other people have done it in 25 operators so I know there is a way. Any ideas?
1) You compute the wrong result; the shift of 31 is missing. 2) You should have used a for loop. 3) Searching a bit for bit counting algorithms would have given you a bunch of links.
精彩评论