C: Sneaky way to count positive bits?

bitwise-operators, c

Solution

The fastest way to count bits is by using "magic numbers":

unsigned int v = 0xCF31; // some number
v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
unsigned int c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

This prints 9 (link to ideone).

This takes 12 operations for 32-bit numbers - the same number a lookup-based method takes, but you do not need a lookup table.

Problem

So I'm trying to see if there's some sneaky series of bit operations that will allow me to count how many bits in a uint32 are 1 (or rather the count mod 2). The "obvious" way would be something like this: ``` uint32 count_1_bits_mod_2(uint32 word) { uint32 i, sum_mod_2; for(i = 0; i < 32; i++) sum_mod_2 ^= word; word >>= 1; ``` Is there some "sneaky" way to get the proper sum_mod_2 without using a loop?

Original source