題目338：比特位計數
示例1：
輸入: 2輸出: [0,1,1]
輸入: 5輸出: [0,1,1,2,1,2]
給出時間復雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時間O(n)內用一趟掃描做到嗎？
要求算法的空間復雜度為O(n)。
你能進一步完善解法嗎？要求在C++或任何其他語言中不使用任何內置函數（如 C++ 中的 __builtin_popcount）來執行此操作。
分析
做此題首先需要知道如何計算一個數的比特位的個數。可以通過(x & x-1)每次消除數字二進制表示形式的最后一個1，代碼如下：
int count(int num) {int n = 0;while (num != 0) {++n;num = (num & num-1);}return n;}
代碼
方法1：
class Solution {public:int count(int num) {int n = 0;while (num != 0) {++n;num = (num & num-1);}return n;}vector<int> countBits(int num) {vector<int> dp(num+1, 0);for (int i = 0; i <= num; ++i) {dp[i] = count(i);}return dp;}};
class Solution {public:vector<int> countBits(int num) {vector<int> dp(num+1, 0);for (int i = 1; i <= num; ++i) {dp[i] = dp[i & (i-1)] + 1;}return dp;}};