Set bit count in a binary number using C

Question

I have got a binary number of length 8 for eg 00110101 There are 8 bits set. I need a fast bit count to determine the number of set bits. Running the algo like this x=x&(x-1) will limit it to the number of set bits in the number contains but I am not very sure as to how to use it.A little help would be appreciable!!

Answer 1

This x=x&(x-1) removes the lowest set bit from the binary string. If you count the number of times you remove the lowest bit before the number becomes 0, you'll get the number of bits that were set.

char numBits(char x){
    char i = 0;
    if(x == 0)
        return 0;
    for(i = 1; x &= x-1; i++);
    return i;
}

Answer 2

doing x = x & (x-1) will remove the lowest bit set. So in your case the iterations will be performed as,

loop #1: 00110101(53) & 00110100(52) = 00110100(52) :: num bits = 1

loop #2: 00110100(52) & 00110011(51) = 00110000(48) :: num bits = 2

loop #3: 00110000(48) & 00101111(47) = 00100000(32) :: num bits = 3

loop #3: 00100000(32) & 00011111(31) = 00000000( 0) :: num bits = 4

The number of iterations allowed will be the total number of bits in the given number.

Answer 3

US Patent 6,516,330 – Counting set bits in data words

(I only invented it -- don't ask me to explain it.)

Answer 4

The method described in the question (generally ascribed to K&R ) has the complexity of n, where n is the number of bits set in the number.

By using extra memory we can bring this to O(1):

Initialize a lookup table with the number of bit counts (compile-time operation) and then refer to it; You can find the method here : Counting bits set by lookup table

You can find a detailed discussion of different methods in Henry S. Warren, Jr.(2007) "The Quest for an Accelerated Population Count", Beautiful Code pp.147-158 O'Reilly