Coders Packet

Total Set Bits in a Number in C++

By mahima mahendru

To find the count of a total number of set bits in the binary representation of an integer in two ways: a simple while loop and by using a built-in library function in C++.

 METHOD 1:

In this method, we use a simple while loop to count the number of set bits in the binary representation of an integer by executing the loop till N>0. In each iteration, we check if the rightmost bit is set or not in N by using bitwise and (&) between N and 1.

Check if N&1 is zero or not. If it is not zero it implies that the bit is set and we increment our counter by 1.Rightshift the integer by 1 position. Counter gives the final value of set bits in the integer.

Example: Let's consider 10, having binary representation as 1010. Here the total number of set bits is 2.

Have a look at the implementation code for better understanding. 

#include
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int main()
{
   
 ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin>>n;
        int counter=0;
        
        // METHOD 1:
        while(n)
        {
            if( n & 1)             //BITWISE AND WITH 1
                counter+=1;        //INCREMENT COUNTER IF BIT IS SET
                n=n>>1           //RIGHTSHIFT THE BITS OR SIMPLY DIVIDE N BY 2
        }
        cout<<counter<<endl;
        
}
 METHOD 2:
In this, we will see the use of STL function __builtin_popcount().
_builtin_popcount(x): This function is used to count the number of one’s(set bits) in an integer.
Have a look at the implementation code for better understanding. 
#include
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int main()
{
   
 ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin>>n;
        int counter;
        
        // METHOD 2:
       counter=__builtin_popcount(n);
        cout<<counter<<endl;
        

}

Download Complete Code

Comments

No comments yet