Thread: Recursion

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