方案三：动态规划——最低有效位
方法二需要实时维护最高有效位，当遍历到的数是 2 的整数次幂时，需要更新最高有效位。如果再换一个思路，可以使用「最低有效位」计算「一比特数」。
对于正整数 $x$，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是
$\lfloor \frac{x}{2}\rfloor$。
如果 $\text{bits}[\lfloor \frac{x}{2}\rfloor ]$的值已知，则可以得到 $\text{bits}[x]$ 的值：
如果 $x$是偶数，则 $\text{bits}[x]=\text{bits}[\lfloor \frac{x}{2}\rfloor ]$；
如果 $x$ 是奇数，则 $\text{bits}[x]=\text{bits}[\lfloor \frac{x}{2}\rfloor ]+1$。
上述两种情况可以合并成：$\text{bits}[x]$ 的值等于 $\text{bits}[\lfloor \frac{x}{2}\rfloor ]$的值加上 $x$ 除以 2 的余数。
由于 $\lfloor \frac{x}{2}\rfloor$可以通过 $x>>1$ 得到，$x$ 除以 2 的余数可以通过 $x\&1$ 得到，因此有：$\text{bits}[x]=\text{bits}[x>>1]+(x\&1)$。
遍历从 1 到 $n$ 的每个正整数 i，计算 $\text{bits}$ 的值。最终得到的数组 $\text{bits}$ 即为答案。

java代码：

/**
     * @param n
     * @return
     */
    public static int[] countBits(int n) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i & (i - 1)] + 1;
        }
        return dp;
    }

    /**
     * 
     * @param n
     * @return
     */
    public static int[] countBits2(int n) {
        int[] dp = new int[n + 1];
        int highbit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highbit = i;
            }
            dp[i] = dp[i - highbit] + 1;
        }
        return dp;
    }

    /**
     *
     * @param n
     * @return
     */
    public static int[] countBits3(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42