Count set bits in C/C++

Counting the number of set bits (1s) in a binary representation of a number is a classic problem in computer science.
It often appears as a subproblem in larger questions. For example, you can refer to LeetCode 762 – Prime Number of Set Bits in Binary Representation.

Let’s explore different approaches to solve it.

Basic Approach (Bit by Bit Checking)

The most straightforward method is to check the last bit and right shift the number until it becomes zero.

int countSetBits(int n) {
    int count = 0;

    while (n > 0) {
        if (n & 1) {   // check last bit
            count++;
        }
        n = n >> 1;    // right shift
    }

    return count;
}

Time Complexity:
O(log n) — because we process each bit once.

Better Approach: __builtin_popcount()

GCC provides a built-in function:
__builtin_popcount(unsigned int n)

It returns the number of set bits in an unsigned integer.

#include <iostream>
using namespace std;

int main() {
    int n = 13;  // Binary: 1101

    cout << "Set bits: " << __builtin_popcount(n);

    return 0;
}

For Long Long Values

If you're working with long long, use:
__builtin_popcountll(n);

🚀 Why Use __builtin_popcount()?

1. Extremely fast (often maps to a single CPU instruction like POPCNT)
2. Cleaner and more readable
3. Ideal for competitive programming