直指OfferII003.前n个数字二进位中1的长度

338. 位计数(javascript)338. Counting Bits

给定非负整数 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

Brian Kernighan 算法的原理是：对于任何整数。 xx，令 x=x&(x-1)x=x & (x−1)，操作将 xx 的最后一个二进制表示 1 变成 0因此 x 重复操作 x 变成 0，操作数为 x “一位”。

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

};

bt = function (p) {
    let sum = 0
    while (p > 0) {
        p &= p - 1
        sum++
    }
    return sum
}

leetcode来源： https://leetcode-cn.com/problems/w3tCBm/