29 February 2008

Function for counting number of bits set to one, in a 32-bit word (in C)

I've found a great way to (efficiently) count number for bits set to one, in a 32-bit word.

So, here's a function:

uint32_t count_nonzero_bits(uint32_t n)
{
uint32_t masks[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF };
for(size_t i=0; i < 5; i++)
{
n = (n & masks[i]) + ((n >> (1 << i)) & masks[i]);
}
return n;
}

It could be easily extended to 64 bits or more, just by adding one (or more) masks.

And here's a link to the original article: http://11011110.livejournal.com/38861.html

No comments: