Given an uint8_t, find out how many bits are set

Question

I do have an 8-bit unsigned integer and I'd like to know how many of its bits are set to 1. There is a trivial way by AND-ing (&) it with 0x01, 0x02, 0x04, 0x08, 0x0F, 0x10, 0x20, 0x40, 0x80, 0xF0 and incrementing a variable for each one of those which is not zero, but I'd like to hear more sophisticated solutions.

Besides @Barry's answer, here some fun methods: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive — Daniel Frey, Apr 10 '15 at 15:31

score 2 · Accepted Answer · answered Apr 10 '15 at 15:30

Use a builtin:

int bits_set(uint8_t x) {
    return __builtin_popcount(x);
}

Or make a table:

int bits_set(uint8_t x) {
    // easy enough to generate this
    static const uint8_t table[] = {0, 1, 1, 2, 1, 2, ... };

    // then it's just a lookup
    return table[x];
}

score 2 · Answer 2 · answered Apr 10 '15 at 15:36

2

You can use a while loop with bitshifting:

uint8_t someInt = 13;
int num_ones = 0;

while (someInt)
{
    num_ones += someInt & 1;
    someInt = someInt >> 1;
}

answered Apr 10 '15 at 15:36

dwcanillas

3,562
2
24
33

Given an uint8_t, find out how many bits are set

2 Answers2