题目:给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1：

// 输入: n = 2
// 输出: [0,1,1]
// 解释:
// 0 --> 0
// 1 --> 1
// 2 --> 10

示例 2：

// 输入: n = 5
// 输出: [0,1,1,2,1,2]
// 解释:
// 0 --> 0
// 1 --> 1
// 2 --> 10
// 3 --> 11
// 4 --> 100
// 5 --> 101

说明:

• 0 <= n <= 105

进阶:

• 给出时间复杂度为 O(n * sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
• 要求算法的空间复杂度为 O(n) 。
• 你能进一步完善解法吗？要求在 C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。

思路分析

本题的解法基于位运算。对于常用的十进制数转换成二进制数，我们可以查看下表。

对于任意的正整数x,按位与操作符有这样的一条性质，那就是如果x & (x - 1) = 0,那么x一定是2的整数次幂。我们以1 & 2为例:

//让对应位数一样，往前面补0
//   01  => 1的二进制数表示
// & 10 => 2的二进制数表示
// ——————————————————————
//    0   => 按位与操作符对应2个操作数，只有当2个位都为1时才是1，否则就是0

根据这条性质，我们可以知道，对于任意的十进制数，始终将x与x - 1执行按位与，其结果本质上就是将最右侧的位数值为1变为0，因此当该结果为0时，执行的操作次数即统计出了1的次数。这种算法也被叫做Brian Kernighan 算法。可能以上的示例看不出这条规律，那么我们再举一个示例，比如求10 & 9。

//位数一样，不需要往前面补0
//   1001  => 9的二进制数表示
// & 1010 => 10的二进制数表示
// ——————————————————————
//   1000   => 按位与操作符对应2个操作数，只有当2个位都为1时才是1，否则就是0

因此，我们可以创建一个长度为n + 1的数组，循环n，然后对每一个循环的迭代值i统计执行x & x - 1的操作次数，即可解答本题。代码如下:

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
    const res = [];
    for(let i = 0;i < n + 1;i++){
        res[i] = countOnes(i);
    }
    // 返回结果
    return res;
};
var countOnes = function(x){
    let count = 0;
    while(x > 0){
        x &= x - 1;
        // 统计次数
        count++;
    }
    return count;
}

以上算法的时间复杂度和空间复杂度分析如下:

• 时间复杂度：O(n * logn)。需要对从 0 到 n 的每个整数使用计算「1的个数」，对于每个整数计算「1的个数」的时间都不会超过 O(n * logn)。
• 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

基于Brian Kernighan 算法，我们可以得出另一种解决思路，那就是动态规划。本题基于动态规划也有三种解法，这里只讲解一种，理解了其中一种，对于其它2种则也能很好的理解，可以点击如下的参考更多思路。

我们定义正整数x的二进制表示中最低/最右侧的1的所在位为[最低设置位]，例如10的二进制表示可以为1010(2),亦可以简写成10(2)。因此其最低设置位为2。令y = x & (x - 1),显然0 <= y < x,对于最后的结果res，则有res[x] = res[y] + 1。因此对于任意的正整数x，则都会有res[x] = res[x & (x - 1)] + 1。基于这条性质，我们可以很快写出如下代码:

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
    // 正整数0中含有1的个数为0，因此动态规划dp[0] = 0;
    const res = [0];
    // 迭代起始值需要从1开始
    for(let i = 1;i < n + 1;i++){
        res[i] = res[i & i - 1] + 1;
    }
    // 返回结果
    return res;
};

以上算法的时间复杂度和空间复杂度分析如下:

• 时间复杂度：O(n)。对于每个整数，只需要O(1)的时间复杂度来计算1的个数。
• 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。