C++ program to count the number of ones in a binary representation of a number














































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













More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 275 1
C++ program to Sort a Linked List Using Merge Sort 258 1
C++ Program to Implement a Linked List representation of a Binary tree 253 1
C++ Program to Check for balanced parentheses in an expression 166 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 213 1
C++ program to print Indian flag 248 1
C++ program to Convert a multi level linked list to a singly linked list 164 1
C++ program to print right view of a Binary tree using queue 183 1
C++ Program to implement Huffman Coding Compression Algorithm 544 1
C++ Program to Create a Height Balanced Binary Tree 186 1
C++ program to implement Prims algorithm 263 1
C++ Program for BFS Traversal 197 1
C++ Progam to Evaluate a Prefix Expression 181 1
C++ Program to Implement Queue using Linked List 191 1
C++ implementation of Stack using Linked list 201 1
C++ program to find the intersection point of two linked lists 243 1
C++ program to count the inversions in the given array 228 1
C++ program to perform D.N.F sort 258 1
C++ program to print all possible subsets of a String 233 1
C++ program to count the number of ones in a binary representation of a number 243 1
C++ program to print all possible subsets of a set 264 1
C++ program to find the largest word in a String 235 1
C++ Program to print a matrix in Spiral order 258 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 249 1
C limits library 277 1
Program to add two Binary numbers 248 1

Comments