C++ Program to Count Set Bits in an Integer

You can count set bits in C++ using a loop with n & 1 to check the last bit and n >>= 1 to shift bits right, like this: int count = 0; while(n) { count += n & 1; n >>= 1; }.

Examples

Input5

OutputNumber of set bits in 5 is 2

Input15

OutputNumber of set bits in 15 is 4

Input0

OutputNumber of set bits in 0 is 0

How to Think About It

To count set bits, think of the number as a sequence of bits. Check the last bit using AND with 1. If it is 1, increase the count. Then shift the number right by one bit to check the next bit. Repeat until the number becomes zero.

Algorithm

1

Get the input number.

2

Initialize a count variable to zero.

3

While the number is not zero:

4

Check if the last bit is 1 by using bitwise AND with 1.

5

If it is 1, increment the count.

6

Shift the number right by one bit.

7

Return the count.

Code

cpp

#include <iostream>
using namespace std;

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

int main() {
    int num = 5;
    cout << "Number of set bits in " << num << " is " << countSetBits(num) << endl;
    return 0;
}

Output

Number of set bits in 5 is 2

Dry Run

Let's trace the number 5 through the code to count set bits.

1

Initial value

n = 5 (binary 0101), count = 0

2

Check last bit

5 & 1 = 1, so count = 1

3

Shift right

n >>= 1 -> n = 2 (binary 0010)

4

Check last bit

2 & 1 = 0, count stays 1

5

Shift right

n >>= 1 -> n = 1 (binary 0001)

6

Check last bit

1 & 1 = 1, count = 2

7

Shift right

n >>= 1 -> n = 0, loop ends

n (decimal)	n (binary)	n & 1	count
5	0101	1	1
2	0010	0	1
1	0001	1	2

Why This Works

Step 1: Check last bit

Using n & 1 isolates the last bit of the number to see if it is set (1).

Step 2: Increment count

If the last bit is 1, we add 1 to the count to keep track of set bits.

Step 3: Shift bits right

Shifting the number right by one bit with n >>= 1 moves the next bit into the last bit position for checking.

Step 4: Repeat until zero

We repeat this process until all bits are checked and the number becomes zero.

Alternative Approaches

Brian Kernighan's Algorithm

cpp

#include <iostream>
using namespace std;

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

int main() {
    int num = 5;
    cout << "Number of set bits in " << num << " is " << countSetBits(num) << endl;
    return 0;
}

This method is faster because it removes the lowest set bit in each iteration, reducing the number of loops to the number of set bits.

Using std::bitset

cpp

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int num = 5;
    bitset<32> b(num);
    cout << "Number of set bits in " << num << " is " << b.count() << endl;
    return 0;
}

This uses C++ standard library's bitset to count set bits easily but may use more memory.

Complexity: O(k) time, O(1) space

Time Complexity

The loop runs once for each bit in the number (k bits), so time is O(k).

Space Complexity

Only a few variables are used, so space is O(1).

Which Approach is Fastest?

Brian Kernighan's method is faster because it loops only as many times as there are set bits, not all bits.

Approach	Time	Space	Best For
Simple bitwise loop	O(k)	O(1)	Easy to understand, small code
Brian Kernighan's Algorithm	O(m) where m = set bits	O(1)	Performance critical code
std::bitset	O(k)	O(k)	Quick coding with standard library