C code to count the number of '1' bits in

Question

I need C code to return the number of 1's in an unsigned char in C. I need an explanation as to why it works if it's not obvious. I've found a lot of code for a 32-bit number but not much for an unsigned char.

Answer 1

See the bit twiddling hacks page: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

there are many good solutions for this.

Also, this function in its simplest implementation is fairly trivial. You should take the time to learn how to do this.

Answer 2

base on Ephemient's post, we have the no branched 8 bits version. It is in hexadecimal expression.

typedef unsigned char       UINT8;
typedef unsigned short      UINT16;
typedef unsigned long long  UINT64;
int hammingWeight8( const UINT8& c)
{
    return ( c* 0x8040201ULL & 0x11111111)%0xF;
}

Apply it twice, we have a 16bits version, which needs 9 operations.

int hammingWeight16( const UINT16& c)
{
    return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + 
             ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}

Here I write a variant 16bits version which needs 64bits registers and 11 operations. It seems not better than the previous one, but it just uses 1 modulo operation.

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}