recursive method in Java

[logistic_guy]

Write a recursive method that returns the number of $\displaystyle 1$’s in the binary representation of $\displaystyle N$. Use the fact that this is equal to the number of $\displaystyle 1$’s in the representation of $\displaystyle N/2$, plus $\displaystyle 1$, if $\displaystyle N$ is odd.

 

[khansaheb]

Write a recursive method that returns the number of $\displaystyle 1$’s in the binary representation of $\displaystyle N$. Use the fact that this is equal to the number of $\displaystyle 1$’s in the representation of $\displaystyle N/2$, plus $\displaystyle 1$, if $\displaystyle N$ is odd.

Please show us what you have tried and exactly where you are stuck.

Please follow the rules of posting in this forum, as enunciated at:

READ BEFORE POSTING

Please share your work/thoughts about this problem

 

[logistic_guy]

In this game, I will have to import the $\displaystyle \text{Scanner}$ class to allow the user to enter a number.

Say, the user entered $\displaystyle 26 = 11010$, my program should output: There are $\displaystyle 3$ ones ($\displaystyle 1\text{'s}$).

 

[logistic_guy]

In this game, I will have to import the $\displaystyle \text{Scanner}$ class to allow the user to enter a number.

Say, the user entered $\displaystyle 26 = 11010$, my program should output: There are $\displaystyle 3$ ones ($\displaystyle 1\text{'s}$).

The process of counting the ones will be done recursively through a function. In other words, a function will call itself multiple times and it will not stop until it reaches a base case.

Our base case will be:

If the number is $\displaystyle 0$ or $\displaystyle 1$, stop.

 

[logistic_guy]

When the user enters a number larger than $\displaystyle 1$, I want that number eventually to get smaller and smaller until it reaches the base case. To handle such a process, I will divide that number by $\displaystyle 2$ continuously.

 

[logistic_guy]

Let us make a simulation for a user who entered the number $\displaystyle 26 = 11010$.

$\displaystyle \text{counter} = 0$

$\displaystyle \text{Step} \ \bold{1}$
if $\displaystyle 26 = 0$ or $\displaystyle 26 = 1$, stop $\displaystyle \rightarrow$ false, then continue.

$\displaystyle \text{Step} \ \bold{2}$
if $\displaystyle 26$ is even, divide by $\displaystyle 2$ $\displaystyle \rightarrow$ true, $\displaystyle \frac{26}{2} = 13$

$\displaystyle \text{Step} \ \bold{3}$
if $\displaystyle 13 = 0$ or $\displaystyle 13 = 1$, stop $\displaystyle \rightarrow$ false, then continue.

$\displaystyle \text{Step} \ \bold{4}$
if $\displaystyle 13$ is odd, divide by $\displaystyle 2$ and add one to the counter $\displaystyle \rightarrow$ true, $\displaystyle \left\lfloor\frac{13}{2}\right\rfloor = 6$ $\displaystyle (\text{counter} = 1)$

$\displaystyle \text{Step} \ \bold{5}$
if $\displaystyle 6 = 0$ or $\displaystyle 6 = 1$, stop $\displaystyle \rightarrow$ false, then continue.

$\displaystyle \text{Step} \ \bold{6}$
if $\displaystyle 6$ is even, divide by $\displaystyle 2$ $\displaystyle \rightarrow$ true, $\displaystyle \frac{6}{2} = 3$

$\displaystyle \text{Step} \ \bold{7}$
if $\displaystyle 3 = 0$ or $\displaystyle 3 = 1$, stop $\displaystyle \rightarrow$ false, then continue.

$\displaystyle \text{Step} \ \bold{8}$
if $\displaystyle 3$ is odd, divide by $\displaystyle 2$ and add one to the counter $\displaystyle \rightarrow$ true, $\displaystyle \left\lfloor\frac{3}{2}\right\rfloor = 1$ $\displaystyle (\text{counter} = 2)$

$\displaystyle \text{Step} \ \bold{9}$
if $\displaystyle 1 = 0$ or $\displaystyle 1 = 1$, stop $\displaystyle \rightarrow$ true, if the number is $\displaystyle 1$, add one to the counter $\displaystyle (\text{counter} = 3)$

And that's how we got the number of ones $\displaystyle = 3$. In fact, that $\displaystyle \text{counter}$ does not exist. The function just calls itself and keeps track of the ones when the number is odd. I put the $\displaystyle \text{counter}$ just to give your brain an imaginary visualization of the process.
Some of you may be wondering, how all this magic happens. In simple words, I have used the concept of the Hamming Weight.

 

[logistic_guy]

We have the whole idea in the pocket, we just need to implement it in Java.

In the next days, I will brainstorm the components that I need in my program, then I will slowly show my code.

Be in touch, and don't be greedy!