前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组
输入: n = 2
输出: [0,1,1]
解释: 0 —> 0 1 —> 1 2 —> 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/w3tCBm

思路
在进行做题的时候发现规律如图所示

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n+1];  // 因为[0,n],闭区间
        int bit = 0;  // 用来记录当前范围2的x次幂 [2的x次幂，2的i+1次幂)
        for(int i = 1;i<=n;i++){
            if((i&(i-1))==0){  // 证明为2的x次幂
                bit = i;
            }
            bits[i] = bits[i-bit]+1;
        }
        return bits;
    }
}

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n+1];
        bits[0] = 0;
        for(int i = 1;i<=n;i++){
            // 如果为2的幂次方，就是消除一个1变成他上一个的个数+1
            bits[i] =bits[i&(i-1)]+1;
        }
        return bits;
    }
}