Count Number of 1's in A Binary Representation of N, RECURSIVELY. in JAVA

Question

I understand the concept that the number of 1's in N is the same as N/2 if it's even, and N/2 + 1 if the number is odd, but I don't understand how to do it recursively.

Also, say I input 10101 into my machine, and I do N/2, it does 505 instead of the binary division. Do I have to convert back and forth each time?

Answer 1

Here's a non-homework way to answer this: Integer.bitCount

:-P

Answer 2

Read the question carefully: The number of 1's in N is the same as the number of 1's in N/2 if N is even, and the same as the (number of 1's in N/2) + 1 if N is odd.

How can you tell if N is even or odd, just by looking at the bit string? (Hint: think about what each column represents: 64's, 32's, 16's, ...)

Think about what N/2 means in terms of the bit operations: compute a few on paper, like 8/2, 7/2, 5/2 and look for a pattern.