Write a recursive function that returns the number of 1's in the binary representation of N? I am not looking for code but what is the math equation or a hint of what I am trying to do mathmatically?
Printable View
Write a recursive function that returns the number of 1's in the binary representation of N? I am not looking for code but what is the math equation or a hint of what I am trying to do mathmatically?
[Hint]
consider a function that checks a specified bit. That function can recursivley check all bits.
[/Hint]
How does this code work? Especially this line return (x & 1) + Power(x/2); What does this character do &?
#include<iostream>
using namespace std;
int Power(int);
int main()
{
int number;
cin>> number;
cout<< Power(number);
return 0;
}
int Power(int x)
{
if(x == 0)
return 0;
else
return (x & 1) + Power(x/2);
}[CODE]
>> What does this character do &?
& is the bitwise 'and', it will 'and' every bit individually...
ex)
1001 & 0011 == 0001
>> Especially this line return (x & 1) + Power(x/2)
this will return x & 1 (as described above) plus the result of calling Power(x/2). At some point x/2 will equal 0 and 0 will be returned to end the recursive cycle.
the code using Iteration is:
Code:/*assume the binary representation of the number will take M bits so we have an array called unsigned num[M]*/
#include <iostream.h>
#define M 10
unsigned num[M];
void convert(unsigned)
{
for(int i=0;i<M;i++)
{
num[i]=(My_Number%2==1);
My_Number/=2;
}
}
int count(unsigned *a)
{
int x=0;
for(int i=0;i<M;i++)
if(num[i]==1)
x++;
return x;
}
int main()
{
unsigned r;
cin >>r;
for(i=0;i<M;i++)
num[i]=0;
convert(r);
int xcount=count(num);
cout <<xcount<<endl;
return 0;
}
There is some good information on bitwise operators in the Programming FAQ.
BITWISE HINTS:
Programmers will usually use hexadecimal when dealing with binary numbers / bit patterns. It's easier (for humans) to do binary-hex conversions than binary-decimal. C++ can use hex natively... binary takes a few more steps. And, it gets difficult (for humans) to read binary numbers when they get longer than 8-bits.
You can use the built-in Windows calculator to do decimal, binary, octal, and hex conversions.
Start -> Programs -> Accessories -> Calculator -> View -> Scientific