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

Comments

[Paul J. Lucas]

You forgot about:

while (n > 0) {
    n &= n - 1;
    ++count;
}

__builtin_popcount() isn't standard. Starting in C23, there are standard functions for this.

[Shubham_Gharage]

Thank you for the information. I came across this compiler builtin function on LeetCode when I saw someone else using it in their solution. While reading more about it, I found this Stack Overflow answer (stackoverflow.com/a/52173703/20260667
), where I realized that it can be more efficient than manually implemented approaches. I thought sharing it might help me understand different perspectives.

During my research, I also came across Brian Kernighan’s Algorithm for counting set bits. I understand that __builtin_popcount() is not part of the C++ standard, but I believe it can be very useful in competitive programming due to its efficiency and simplicity.

Thank you Again!