Counting Bits

1class Solution {
2    public int[] countBits(int n) {
3        int[] res = new int[n + 1];
4        int pow = 1; // Current power of two
5        int x = 1;   // Index at current power level
6
7        for (int i = 1; i <= n; i++) {
8            if (i == pow) {
9                pow *= 2; // Move to next power of two
10                x = i;
11            }
12            res[i] = res[i - x] + 1;
13        }
14        return res;
15    }
16}