Count the number of bits set using only bitwise operations

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.

链接地址: http://www.djcxy.com/p/72602.html

上一篇: 在32位计数设置位的方法的说明

下一篇: 对仅使用按位运算设置的位数进行计数