Math Bit Manipulation
Learner Level

Implement the countBitsUpToNSum method that returns the total count of set bits for all numbers from 0 to n.

The input is an integer n.

For every number from 0 to n, count how many set bits are present in its binary representation. Your task is to return the sum of all these bit counts.

For example, from 0 to 5, the bit counts are 0, 1, 1, 2, 1, 2. Their sum is 7.

Example 1
Input:
n (int) = 5
Return:
(int) 7
Example 2
Input:
n (int) = 2
Return:
(int) 2
Example 3
Input:
n (int) = 0
Return:
(int) 0

Use dynamic programming to reuse previous bit counts.

For any number i, the number of set bits is bits[i / 2] + (i % 2). This works because dividing by two removes the last binary bit, and i % 2 tells whether the removed bit was 1.

Add each computed count to the total and return the total.

Pseudocode:

function countBitsUpToNSum(n):
    bits = array of size n + 1 filled with 0
    total = 0
    for i from 1 to n:
        bits[i] = bits[i / 2] + (i % 2)
        total = total + bits[i]
    return total
Run your code to see the result.