Recursion

This is a discussion on Recursion within the C++ Programming forums, part of the General Programming Boards category; Write a recursive function that returns the number of 1's in the binary representation of N? I am not looking ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    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?

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    [Hint]
    consider a function that checks a specified bit. That function can recursivley check all bits.
    [/Hint]

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    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]

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >> 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.

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    7

    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;
    }

  6. #6
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398

    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 01:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21