338.3.js

//给定一个非负整数num，对于每个数字i而言，0<= i <=num，计算每个数字的
//二进制表示中1的个数，并将结果作为一个数组返回
//解法是实现一个countBit，对任意非负整数你，计算它的二进制表示中1的个数
//从0循环到num，求出每个的值，将其放在数组中返回。
//很容易就可以得到一个时间复杂度为O(n*sizeof(integer))的算法，但是可以得到一个O(n)时间复杂度的算法吗？
//空间复杂度应该为O(n)
//可以将这个算法写成一个万能公式，不需要使用任何语言内置的统计函数
//基于一个定律，我们可以得到一个比2中更快的解法
//定律：对于任意n，n>=1，有如下等式成立
//countBit(n & (n - 1)) === countBit(n) -1
//对于任意n，n-1的二进制数表示刚好是n的二进制数的最末一个“1”退位。因此n&n-1正好将n的最末一位“1”消去。
//6 的二进制数是 110， 5 = 6 - 1 的二进制数是 101，6 & 5 的二进制数是 110 & 101 == 100
//88 的二进制数是 1011000，87 = 88 - 1 的二进制数是 1010111，88 & 87 的二进制数是 1011000 & 1010111 == 1010000
/**
 * @param {number} num
 * @return {number[]}
 */
function countBit(n) {
    var ret = 0;
    while (n > 0) {
        //累加计算1的个数
        ret++;
        //每做一次这个运算，n会去掉自己中的一个1，且会变小，变小的幅度是变化的
        n &= n - 1;
    }
    return ret;
}
var countBits = function (num) {
    var ret = [];
    for (var i = 0; i < num; i++) {
        ret.push(countBit(i));
    }
    return ret;
};