Exercism c++ problem

Projects Programming
5

We can count the number of set bits (1s) in the binary representation of a number without using any built-in bit-counting functions. A common and efficient way to do this is using Brian Kernighan's Algorithm .

The idea is to repeatedly turn off the rightmost set bit of the number until the number becomes 0. Each time we turn off a bit, we increment a counter. The operation n & (n - 1) clears the least significant set bit of n .

For example:
If n = 6 (binary 0110 ):

  1. n & (n - 1) => 0110 & 0101 => 0100 (n becomes 4, count = 1)
  2. n & (n - 1) => 0100 & 0011 => 0000 (n becomes 0, count = 2)
    The loop stops. The count is 2, which is correct for the number 6.
#include <iostream>

// Function to count set bits using Brian Kernighan's Algorithm
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // Clear the least significant set bit
        count++;
    }
    return count;
}
1 Like