# Recursion

• 08-20-2003
Drew
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?
• 08-20-2003
Perspective
[Hint]
consider a function that checks a specified bit. That function can recursivley check all bits.
[/Hint]
• 08-20-2003
Drew
Recursion
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]
• 08-20-2003
Perspective
>> 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.
• 08-21-2003
Ibn Aljazeera
code
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; }```
• 08-21-2003
DougDbug
Bitwise operators...
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