338.比特位记数(javascript)338.CountingBits

剑指 Offer II 003. 前 n 数字二进制 1 的个数

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

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

示例 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

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
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) {
//创建长度n+1新阵列，同时使用0填充
    let myList = new Array(n + 1).fill(0)
    for (let i = 0; i <= n; i++) {
        myList[i] = bt(i)
    }
    return myList
};
var bt = function (p) {
    let one = 0
    while (p > 0) {
        p &= (p - 1)
        one++
    }
    return one;
}

leetcode题： https://leetcode-cn.com/problems/counting-bits/