C++ program to count the number of ones in a binary representation of a number
Introduction:
In this program the user enters a number as an input and then the program outputs number of one's present in the binary representation of that number.
Algorithm:
Here we use the concept of the Bit Manupulation. Let us assume a number n, the difference between the nth number and n-1th number is the rightmost setbit that is :Example :n=19 then n=(19)10 = (10011)2 , n-1=(18)10 = (10010)2 .The difference between both the numbers is only the right most set bit that is 1.Now to count the number the number of one in the given number we perform 'AND' operation of the n&n-1 then take the result of this operation and then again perform n&n-1 to it .We perform this operation until the and operation results in zero. Let us understand this with an example:
0th iteration:
n=(19)10 = (10011)2 , n-1=(18)10 = (10010)2
n=n&n-1
=10011 & 10010
=10010 = (18)
1st iteration:
n=(18)10 = (10010)2,n-1=(17)10 = (10001)2
n=n&n-1
=10010 & 10001
=10000 =(16)
2nd iteration:
n=(16)10 = (10000)2,n-1=(15)10 = (1111)2
n=n&n-1
=01000 & 01111
=00000 =(0)
Finally we print the number of iterations or no of times we performed the operation n&n-1.
PROGRAM:
#include <iostream>
using namespace std;
int numberofones (int n) {
int count=0;
while(n) {
n= n & (n-1);
count++;
}
return count;
}
int main(){
int k;
cout<<"enter the number"<<endl;
cin>>k;
cout<<"number of one's present in binary representation of "<<k<<" is : "<<numberofones (k)<<endl;
return 0;
}
OUTPUT:
enter the number
19
number of one's present in binary representation of 19 is : 3
Comments