Recursion using c++

[Joshua Schweigert]

Hello All,
I am asked to create a recursion function that will tell how many ones are in the binary representation of the variable N. So if a user input 4 it would tell them there are one ones. It also says use the fact that this is equal to the number of ones in the representation of N/2 + 1, if N is odd.

Perhaps a point in the right direction would be helpful, I understand the theoretic concept just coding it is my trouble.

Thanks!

[kbw]

You function should check bit zero, right shift the value and call itself until the number passed in is zero.

[a k n]

Hint: use a mask = 1 ; iterate through each bit using a for loop (int i = 0 ; i < sizeof(int)*8 -1 ; i++)
{
if(number&(mask<<i))
//bit is one
else
//bit is zero
}
Edit : oh i see you need recursion then implement the above loop using a recursive function.

[keskiverto]

It also says use the fact that this is equal to the number of ones in the representation of N/2 + 1, if N is odd.

I bet it says:

If N is odd, then f(N) = f(N/2) + 1. Else f(N) = f(N/2).

That should help see why recursion can be used.

[ShodanHo]

unsigned
countBits(unsigned num)
{
  if (num == 0)
    return 0;

  if (num & 1)
    return 1 + countBits(num >> 1);

 return countBits(num >> 1);
}

This code returns the sum of the least significant bit and the remainder of the bits recursively until no more bits are set.

So if the number being tested is 10 decimal (1010 binary), then the call will go something like this:
countBits(10) = countBits(5) = 1 + countBits(2) = 1 + countBits(1) = 1 + 1 = 2.

It's important that the number be unsigned so that the top bit does not propagate indefinitely.

The test code for this would be:

int
main(int, char **argv)
{
  std::cout << countBits(0) << std::endl;
  std::cout << countBits(1) << std::endl;
  std::cout << countBits(2) << std::endl;
  std::cout << countBits(3) << std::endl;
  std::cout << countBits(4) << std::endl;
  std::cout << countBits(5) << std::endl;
  std::cout << countBits(-1) << std::endl;

  return 0;
}

The output is:

0
1
1
2
1
2
32

[S G H]

Don't get me wrong, lately I like to shorten functions.

unsigned countBits(unsigned c)
{
    return (c==0)?0:((c&1)?(countBits(c>>1)+1):countBits(c>>1));
}

[ne555]

Then do it

unsigned countBits(unsigned c)
{
    return c? c%2 + countBits(c/2): 0;
}

[S G H]

^ Din't think bout that.