Alex Rivera | Logout

C: Sneaky way to count positive bits?

Asked 2012-08-21T12:21:48.297
8

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?

c bitwise-operators
Edit
Report

1 Answer

7

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.

answered 2012-08-21T12:32:58.830

Your Answer