How to check the number of set bits in an 8-bit unsigned char?

Question

So I have to find the set bits (on 1) of an unsigned char variable in C?

A similar question is How to count the number of set bits in a 32-bit integer? But it uses an algorithm that's not easily adaptable to 8-bit unsigned chars (or its not apparent).

Answer 1

The algorithm suggested in the question How to count the number of set bits in a 32-bit integer? is trivially adapted to 8 bit:

int NumberOfSetBits( uint8_t b )
{
     b = b - ((b >> 1) & 0x55);
     b = (b & 0x33) + ((b >> 2) & 0x33);
     return (((b + (b >> 4)) & 0x0F) * 0x01);
}

It is simply a case of shortening the constants the the least significant eight bits, and removing the final 24 bit right-shift. Equally it could be adapted for 16bit using an 8 bit shift. Note that in the case for 8 bit, the mechanical adaptation of the 32 bit algorithm results in a redundant * 0x01 which could be omitted.

Answer 2

The fastest approach for an 8-bit variable is using a lookup table.

Build an array of 256 values, one per 8-bit combination. Each value should contain the count of bits in its corresponding index:

int bit_count[] = {
// 00 01 02 03 04 05 06 07 08 09 0a, ... FE FF
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, ..., 7, 8
};

Getting a count of a combination is the same as looking up a value from the bit_count array. The advantage of this approach is that it is very fast.

You can generate the array using a simple program that counts bits one by one in a slow way:

for (int i = 0 ; i != 256 ; i++) {
    int count = 0;
    for (int p = 0 ; p != 8 ; p++) {
        if (i & (1 << p)) {
            count++;
        }
    }
    printf("%d, ", count);
}

(demo that generates the table).

If you would like to trade some CPU cycles for memory, you can use a 16-byte lookup table for two 4-bit lookups:

static const char split_lookup[] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};

int bit_count(unsigned char n) {
    return split_lookup[n&0xF] + split_lookup[n>>4];
}

Demo.

Answer 3

I think you are looking for Hamming Weight algorithm for 8bits? If it is true, here is the code:

unsigned char in = 22; //This is your input number
unsigned char out = 0;
in = in - ((in>>1) & 0x55);
in = (in & 0x33) + ((in>>2) & 0x33);
out = ((in + (in>>4) & 0x0F) * 0x01) ;

Answer 4

Counting the number of digits different than 0 is also known as a Hamming Weight. In this case, you are counting the number of 1's.

Dasblinkenlight provided you with a table driven implementation, and Olaf provided you with a software based solution. I think you have two other potential solutions. The first is to use a compiler extension, the second is to use an ASM specific instruction with inline assembly from C.

For the first alternative, see GCC's __builtin_popcount(). (Thanks to Artless Noise).

For the second alternative, you did not specify the embedded processor, but I'm going to offer this in case its ARM based.

Some ARM processors have the VCNT instruction, which performs the count for you. So you could do it from C with inline assembly:

inline
unsigned int hamming_weight(unsigned char value) {
    __asm__ __volatile__ (
            "VCNT.8"
            : "=value"
            : "value"
    );

    return value;
}

Also see Fastest way to count number of 1s in a register, ARM assembly.

---

For completeness, here is Kernighan's bit counting algorithm:

int count_bits(int n) {
    int count = 0;
    while(n != 0) {
        n &= (n-1);
        count++;
    }
    return count;
}

Also see Please explain the logic behind Kernighan's bit counting algorithm.

Answer 5

I made an optimized version. With a 32-bit processor, utilizing multiplication, bit shifting and masking can make smaller code for the same task, especially when the input domain is small (8-bit unsigned integer).

The following two code snippets are equivalent:

unsigned int bit_count_uint8(uint8_t x)
{
    uint32_t n;
    n = (uint32_t)(x * 0x08040201UL);
    n = (uint32_t)(((n >> 3) & 0x11111111UL) * 0x11111111UL);
    /* The "& 0x0F" will be optimized out but I add it for clarity. */
    return (n >> 28) & 0x0F;
}

/*
unsigned int bit_count_uint8_traditional(uint8_t x)
{
    x = x - ((x >> 1) & 0x55);
    x = (x & 0x33) + ((x >> 2) & 0x33);
    x = ((x + (x >> 4)) & 0x0F);
    return x;
}
*/

• This produces smallest binary code for IA-32, x86-64 and AArch32 (without NEON instruction set) as far as I can find.
• For x86-64, this doesn't use the fewest number of instructions, but the bit shifts and downcasting avoid the use of 64-bit instructions and therefore save a few bytes in the compiled binary.
• Interestingly, in IA-32 and x86-64, a variant of the above algorithm using a modulo ((((uint32_t)(x * 0x08040201U) >> 3) & 0x11111111U) % 0x0F) actually generates larger code, due to a requirement to move the remainder register for return value (mov eax,edx) after the div instruction. (I tested all of these in Compiler Explorer)

Explanation

I denote the eight bits of the byte x, from MSB to LSB, as a, b, c, d, e, f, g and h.

                               abcdefgh
*   00001000 00000100 00000010 00000001 (make 4 copies of x
---------------------------------------  with appropriate
abc defgh0ab cdefgh0a bcdefgh0 abcdefgh  bit spacing)
>> 3                                   
---------------------------------------
    000defgh 0abcdefg h0abcdef gh0abcde
&   00010001 00010001 00010001 00010001
---------------------------------------
    000d000h 000c000g 000b000f 000a000e
*   00010001 00010001 00010001 00010001
---------------------------------------
    000d000h 000c000g 000b000f 000a000e
... 000h000c 000g000b 000f000a 000e
... 000c000g 000b000f 000a000e
... 000g000b 000f000a 000e
... 000b000f 000a000e
... 000f000a 000e
... 000a000e
... 000e
    ^^^^ (Bits 31-28 will contain the sum of the bits
          a, b, c, d, e, f, g and h. Extract these
          bits and we are done.)

Answer 6

Maybe not the fastest, but straightforward:

int count = 0;

for (int i = 0; i < 8; ++i) {
    unsigned char c = 1 << i;
    if (yourVar & c) {
        //bit n°i is set
        //first bit is bit n°0
        count++;
    }
}

Answer 7

For 8/16 bit MCUs, a loop will very likely be faster than the parallel-addition approach, as these MCUs cannot shift by more than one bit per instruction, so:

size_t popcount(uint8_t val)
{
    size_t cnt = 0;
    do {
        cnt += val & 1U;    // or: if ( val & 1 ) cnt++;
    } while ( val >>= 1 ) ;
    return cnt;
}

For the incrementation of cnt, you might profile. If still too slow, an assember implementation might be worth a try using carry flag (if available). While I am in against using assembler optimizations in general, such algorithms are one of the few good exceptions (still just after the C version fails).

If you can omit the Flash, a lookup table as proposed by @dasblinkenlight is likey the fastest approach.

Just a hint: For some architectures (notably ARM and x86/64), gcc has a builtin: __builtin_popcount(), you also might want to try if available (although it takes int at least). This might use a single CPU instruction - you cannot get faster and more compact.

Answer 8

Allow me to post a second answer. This one is the smallest possible for ARM processors with Advanced SIMD extension (NEON). It's even smaller than __builtin_popcount() (since __builtin_popcount() is optimized for unsigned int input, not uint8_t).

#ifdef __ARM_NEON
/* ARM C Language Extensions (ACLE) recommends us to check __ARM_NEON before
   including <arm_neon.h> */
#include <arm_neon.h>

unsigned int bit_count_uint8(uint8_t x)
{
    /* Set all lanes at once so that the compiler won't emit instruction to
       zero-initialize other lanes. */
    uint8x8_t v = vdup_n_u8(x);
    /* Count the number of set bits for each lane (8-bit) in the vector. */
    v = vcnt_u8(v);
    /* Get lane 0 and discard other lanes. */
    return vget_lane_u8(v, 0);
}
#endif