Complexity should be less than O(n);

+4 votes

0 votes

uint bit_count(uint value)

{

printf("0x%08X has ", value, value);

value = (value & 0x55555555) + ((value & 0xaaaaaaaa) >> 1);

value = (value & 0x33333333) + ((value & 0xcccccccc) >> 2);

value = (value & 0x0F0F0F0F) + ((value & 0xF0F0F0F0) >> 4);

value = (value & 0x00FF00FF) + ((value & 0xFF00FF00) >> 8);

value = (value & 0x0000FFFF) + ((value & 0xFFFF0000) >> 16);

printf("%d bits set.\n", value);

return value;

}

...

http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer