原题传送门:->132 Pattern

Description

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).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

思路:重点在进位上。

比如 01(1)，它的下一个数字是10(2)，会有一位进位。那么2的比特数和1相等。
并且，相邻两个以“01”结尾的数字相差4。（1、5、9…），也就是步长为4

011会有两位进位。 比特数减一。 步长为8
0111会有三位进位。比特数减二。 步长为16。
那么我们可以把这些进位数预先计算好。

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int>ans(num+1,0);
        int base = 1, step = 4;
        for(int i = 1; base <= num; ++i){
            step = 2 << i;
            for(int j = base+1; j <= num; j+=step){
                ans[j] = -i;
            }
            base += (1 << i);
        }//计算进位数。
        for(int i = 1; i <= num; ++i){
            ans[i] += (ans[i-1]+1);
        }
        return ans;
    }
};

第一层循环，处理后的ans结果大致是:
（0, 0, -1, 0, -2, 0, -1, 0, -3, 0, -1, 0, -2, …)
ans[2]=-1的意思是:1到2产生了一位进位。