Bitwise nuggets: count set bits
Post
Cancel

# 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.