[Java] Count number of bits set to 1

Given a positive integer N, find for each integer in range 0..N inclusive, how many bits are set to 1.

We could for each integer in range 0..N consider its binary representation and pick off all bits set to 1 counting them.
This would make us do at most 32 operations for each number, being 32 a constant we'd have linear time but performance is still impacted.

We can however reuse information we stored earlier (especially in this case it's part of our answer anyway)
Drawing the binary sequence for 0..8 gives us:

• 0: 0000
• 1: 0001
• 2: 0010
• 3: 0011
• 4: 0100
• 5: 0101
• 6: 0110
• 7: 0111
• 8: 1000

And we notice that N and N*2 have exactly the same amount of bits set, just shifted left one position, example:

• 3 and 6
• 2, 4 and 8

What is left out is odd numbers like 5 and 7. But in that case, it's just about setting the lsb to 1 from the previous number, example:

• 5 = 4 + 1
• 7 = 6 + 1

so to create an odd N, we can simply start from N/2, shift it up one position AND check if we should set the lsb to 1 in this new number.
 

If we know how many bits are set in N/2, we skip all of this process and just reuse that value adding one to it if the lsb should be 1. We know if it should be 1 by checking N & 1.

This is also equal to saying number of bits set in N is N/2 + N mod 2 as anything modulo 2 will always be either 0 or 1, specifically 0 if N is even and 1 if N is odd.

We repeat this process for all numbers in our range and we have the solution.

Since the output is part of the solution, our space complexity is O(1) and our time is O(N).

All operations we use are division by 2 and modulo by 2, which are a right bit shift and a bitwise AND.

You can check my implementation of countOnes on my Gist along with some tests in CountOnesJTests.