338. 比特位计数(中等) - https://leetcode-cn.com/problems/counting-bits/submissions/

[tailgo]

先找一下规律，

0 -> 0 -> 0
1 -> 1 -> 1
2 -> 10 -> 1
3 -> 11 -> 2
4 -> 100 -> 1
5 -> 101 -> 2
6 -> 110 -> 2
7 -> 111 -> 3
......

可以得到规律就是 2 和 3 的二进制是在 0 和 1 的二进制最前面加 1，同理 47 是在 03 的最前面加 1 ，那么就可以以 0 和 1 的二进制个数为基础推算出每个数字的二进制数的 1 的个数。

执行用时 : 140 ms, 在Counting Bits的JavaScript提交中击败了96.63% 的用户
内存消耗 : 39.6 MB, 在Counting Bits的JavaScript提交中击败了57.58% 的用户

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
    if (num == 0) return [0];
    if (num == 1) return [0, 1];
    var result = [0, 1];
    
    var gap = 2;
    
    while (true) {
        for (var i = gap; i < 2 * gap; ++i) {
            result[i] = result[i - gap] + 1;
            
            if (i == num) {
                return result;
            }
        }
        gap *= 2;
    }
};

[tailgo]

根据一个公式 i & (i - 1)，会把这个二进制数最右边的 1 去掉，也就是说 i 里面 1 的个数比 i & (i - 1) 多 1。

执行用时 : 144 ms, 在Counting Bits的JavaScript提交中击败了94.38% 的用户
内存消耗 : 39.9 MB, 在Counting Bits的JavaScript提交中击败了30.30% 的用户

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
    var result = [0];
    for (var i = 1; i <= num; ++i) {
        result[i] = result[i & (i - 1)] + 1;
    }
    return result; 
};