Problem 2 Number of 1s in the binary representation Write a

Problem 2: Number of 1s in the binary representation

Write a program that computes the number of 1s in the binary representation of an input number N. Prompt user for the input N. You must solve the problem in a recursive fashion. (Hint: Use the fact that this is equal to the number of 1s in the representation of N/2, plus 1 if N is odd. )

Sample input: 23

Sample output: 4

Solution

#include<iostream>
using namespace std;

int count1s(int number)
{
//If number is 0 then there are 0 ones
if(number==0)
return 0;
//Check the last bit is 1 or not if it is add 1 to the count and divide the number by 2
//Else just divide the number by 2
else
if(1 & number)
return 1+count1s(number>>1);
else
return count1s(number>>1);
}

int main()
{
int number;
cout << \"Input a number : \";
cin >> number;
cout << \"Number of 1\'s in binary representaion of \" << number << \" is \" << count1s(number) << endl;
return 0;
}

OUTPUT:

Input a number : 23

Number of 1\'s in binary representaion of 23 is 4