338. Counting Bits

算法
位操作, 动态规划 
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num 
calculate the number of 1's in their binary representation and return them as an array.

Example 1:
Input: 2
Output: [0,1,1]

Example 2:
Input: 5
Output: [0,1,1,2,1,2]

Follow up: It is very easy to come up with a solution with run time O(n*sizeof(integer)). 
But can you do it in linear time O(n) /possibly in a single pass? Space complexity should be O(n).

用递归计算每一个数的二进制再计数不能满足题目的时间复杂度O(n) 一种巧妙的思路是:
1的个数 = 除了最低位之外的1的个数 + 最低位1的个数
即 $result[i] = result[i>>1] + i \% 2$

1
2
3
4
5
6
7
var countBits = function(num) {
    var result = [0]
    for(var i=1; i<=num; i++){
        result[i] = result[i>>1] + i %2
    }
    return result
};