求star

题目#

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

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

提示：

• 0 <= n <= 105

解题:key:#

① Brian Kernighan算法#

TIP

​ Brian Kernighan算法：对于任意整数 x，令 x=x & (x-1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x的「一比特数」。

var countBits = function(n) {
    const bits = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        bits[i] = countOnes(i);
    }
    return bits
};

const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}

②动态规划-最高有效位#

var countBits = function(n) {
    const bits = new Array(n + 1).fill(0);
    // 最高有效位(小于n并且是2的整数次幂)
    let highBit = 0;
    for (let i = 1; i <= n; i++) {
        // 利用方法1中提到的 i & (i-1)判断是否
        if ((i & (i - 1)) == 0) {
            //	说明i 是 2的整数次幂
            highBit = i;
        }
        bits[i] = bits[i - highBit] + 1;
    }
    return bits;
};