Count Set Bits in an Integer

Code

#include <stdio.h>

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

int main() 
{
    int n;
    scanf("%d", &n);
    printf("%d", countSetBits(n));
    return 0;
}

Solving Approach

This function implements Brian Kernighan’s Algorithm, which is one of the most efficient ways to count the number of "set bits" (bits with a value of 1) in an integer.

While a standard approach might check every single bit one by one, this algorithm is optimized to only run as many times as there are 1s in the number.

1. The Core Logic: n &= (n - 1)

The "magic" of this algorithm lies in the expression n & (n - 1).

In binary, subtracting 1 from a number flips all the bits to the right of the rightmost set bit (including the bit itself). When you perform a Bitwise AND between the original number and this new value, it effectively clears the lowest set bit to zero.

2. Step-by-Step Execution

The function uses a while loop that continues as long as n is not zero:

1. Increment Count: Every time the loop runs, it means we have found a 1.

2. Clear the Bit: The operation n &= (n - 1) removes the rightmost 1 from the binary representation.

3. Repeat: The loop continues until all 1s have been cleared and the number becomes 0.

3. Comparison of Efficiency

If you are working on performance-critical systems (like your DEV 2 firmware projects), efficiency matters:

Example: If the input is the number 8 (binary 1000), a standard loop runs 32 times, but this algorithm runs exactly once.

4. Why This Matters in Firmware

In embedded systems or CAN bus communication, you often need to check:

• Parity bits for error detection.

• Popcount (Population Count) for data compression or signal processing.

• Flag status registers where multiple bits might be active at once.

This algorithm provides a high-speed way to get those answers while consuming minimal CPU cycles.