Count set bits in an 8-bit 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, the popcount aka population count. 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.

Unlike Count the number of set bits in a 32-bit integer, I only have 8-bit integers, so O(log width) bithack methods still have several steps and might not be better than O(set_bits) or 4-bit or 8-bit lookup tables on CPUs without hardware popcount, or if compiling in a way that can't take assume support.

Locomotive

there are only 4 bits set in your example – Fourier

And... gurmeet.net/puzzles/fast-bit-counting-routines – Fourier

Are you looking for the hamming weight? – Sloop

#109523 – Zobias

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;
}

Megacycle

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.

Bebebebeerine

Answer 3

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

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

Farra

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

Following

Answer 5

I have this code snippet works with unsigned integer only: Hope this helps.

uint G = 8501; //10 0001 0011 0101
uint g = 0;

for (int i = 0; i < 32; i++)
{
  g += (G << (31 - (i % 32))) >> 31;
}

Console.WriteLine(g); //6

Span

Answer 6

Depending on how you count the set bits - the number of really set bits are 4 in our case; the bit-width (which I hereby define as the number of the highest bit set plus 1) is 6 (as you need 6 bits to represent your number). The latter one can be determined with

char highestbit (uint32_t num)
{
    char i;
    for (i = 0; i < sizeof(num)*8; i++) {
        if ((1L << i) > num) {
            return i;
        }
    }
    return sizeof(num)*8;
}

(untested)

Ghat

Answer 7

x := (x and $55555555) + ((x shr 1) and $55555555); 
x := (x and $33333333) + ((x shr 2) and $33333333); 
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F); 
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF); 
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);

Taken from matrix67's blog, which is in Chinese.

Kheda

Which looks suspiciously like the above patent. – Farra

@Daniel R Hicks. I hope for your sake the above does not correspond to your patented method. The above method is also described as: Counting bits set in parallel, the quoted references pre-date your patent application. – Elegancy

As with most software patents, the devil is in the details. The attorneys add enough qualifiers to chisel out a "unique" invention (though in this case I didn't really want to go forward with the patent but the other inventor insisted). I have, however, authored several patents that I'm relatively confident are "clean", including 5,001,477 – Encoding variable length and null data while preserving sort sequence, and I've had a couple of others that were clearly "unique" and "new" rejected by patent examiners who had a bug up their arse. – Farra