New to Java - Converting to Binary, Counting 1's, Recursive

Question

Hey Everyone

I just started Data Structures and Algorithms which is taught in Java. So far I've only learned C++ in my life so I'm still VERY new to using java.

Anyways I have a homework problem I'm a little stuck on:

Write a recursive method that returns the number of 1's in the binary representation of N. Use the fact that this is equal to the number of 1's in the representation of N/2 + 1, if N is odd.

Now i'm not sure how exactly to do this. I already have a function set up that takes an integer and converts it to binary and stores it in a string, yet the rest I'm kinda lost on.

If I can get some guidance, that would really help.

This is what I have so far:

import java.io.*;
public class Homework1Code {
  static void prtbinary(String Molly, int size){
    if(size <=0){
      return;
    }
  }

  public static void main(String[] args) {
    int i = 38;
    String binstr = Integer.toBinaryString(i);
    System.out.println("The Original Decimal Number is: " + binstr);
    prtbinary(binstr, binstr.length());
  }
}

Thanks

Answer 1

This is not a hard problem to solve. What you need to do is stop writing code and first solve the problem on paper. Then convert your algorithm to code.

Answer 2

first, reduce the problem to the easiest case ...

Answer 3

The question is about doing arithmetic, so leave the value as an int rather than convering to a string.

Then there are two facts (for non-negative numbers):

• if N is odd then the number of ones is the same as in N/2 plus the one remainder;
• if N is even then the number of ones is the same as in N/2.

bitCount of 010101 is bitCount of 010101/2 = 01010 plus 1 bitCount of 010100 is bitCount of 010100/2 = 01010

Rinse and repeat until finished (induction).

Just don't look at the source to Integer.bitCount.

Answer 4

Step one: think!

It is very hard to write a recursive method whose return type is void.