Bitwise nuggets: count set bits

If we want to count the number of set bits (i.e. bits that are 1) in an int, we can check whether its least significant bit (LSB) is 1, count it as set if applicable, then right-shift the int by one position until we’ve seen the number of bits in an int.

Here is how this can be implemented in C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <stdio.h>
#include <limits.h>

// Returns the number of "on" bits (bits set to 1) in the input `number`.
unsigned int count_set_bits(int number)
{
    unsigned int n_bits_on = 0;

    int value = number;

    for (size_t i = 0; i < CHAR_BIT * sizeof(int); i++) {
        if ((1 & value) == 1)
            ++n_bits_on;
        value >>= 1;
    }

    return n_bits_on;
}

int main()
{
    int numbers[] = {7, 2019, -1, -2};
    for (int i = 0; i < 4; i++)
        printf("count_set_bits(%4d) = %2d\n", numbers[i], count_set_bits(numbers[i]));
}

At line 11, we iterate for the number of bits in an int, which can also be written as CHAR_BIT (macro constant defined in limits.h that represents the number of bits in a char, i.e. 8) multiplied by the number of bytes in an int (which is sizeof(int)).

Here is the output of the above program:

1
2
3
4

count_set_bits(   7) =  3
count_set_bits(2019) =  8
count_set_bits(  -1) = 32
count_set_bits(  -2) = 31

Want to see more bitwise logic? There’s a whole repository on my GitHub on bit fiddling.