C++ Program to Count the Number of Set Bits in a Number

The easy solution to this problem is to convert the given number into a binary string. Loop over all the characters in the string. A number of ones in the string are nothing but the total set bits.

But, we want to find the optimal solution to this problem. We can use the AND operation to find the number of set bits. I will explain to you how you can do that.

Explanation:

Have you observed one thing? If we ‘bitwise AND’ a number n with a number (n-1) then the rightmost set bit or a least significant set bit of a number n is unset or set to zero.

Let’s understand it with the example:

n=6 (0110)

n-1 = 5 (0101)

n = n & n-1  (0100) 

Here we can see the rightmost set bit (3rd bit) of 6 is unset after performing logical AND with 5.

So using this trick we can calculate the number of set bits in the number.

Algorithm and Approach:

1. Set count=0.
2. Perform the logical AND between given n and n-1. (says result=a)
3. Increment count by one.
4. If a is not zero, follow step 1. Else, print count.

If you understand the logic, you can implement it with any programming language of your choice like C/C++, Java, Python, etc.

This trick is very handy while solving competitive coding challenges.

C++ Code:

#include <iostream>
using namespace std;
 
int main()
{
    int n = 6 , count=0;

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

    cout<<"The number of set bits: "<<count
    return 0;
}

Output:

The number of set bits: 2

To improve your bit manipulation skills, check the set of bit manipulation interview questions in data structure coding questions.

Om Tayade

I'm pursuing B.Tech in Computer Science from Pune Institute of Computer Technology. I'm avid learner and enthusiastic programmer.