思考:
1.普通的方法，用除法餘數
2.用bit操做和DP概念，(i & 1)判斷尾數是不是1，用(i/2)的1數量得到扣掉最後一位元外的1數量

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n+1,0);
        for(int i = 0; i <=n; i++){
            int count = 0;
            int temp = i;
            while(temp >= 1){
                if(temp % 2 == 1){
                    count++;
                }
                temp /= 2;
            }
            ans[i]=count;
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n+1, 0); // 創建一個大小為 n+1 的 vector，並初始化所有元素為 0
        
        for (int i = 1; i <= n; i++) {
            int x = ans[i >> 1]; // x = i/2 的位置上的數字的二進制表示中的 1 的個數
            // 若 i 的最後一個位元為 0，則 ans[i] = ans[i/2]（即 x）
            // 若 i 的最後一個位元為 1，則 ans[i] = ans[i/2] + 1（即 x+1）
            ans[i] = (i & 1) == 0 ? x : x + 1;
        }
        //用 and 檢查 最後一個位元是不是 1 
        return ans; // 回傳結果
    }
};


// 8 = 1 0 0 0, 有1個1, 判斷尾數
//29 = 1 1 1 0 1, 14 = 1 1 1 0 有三個1, 且尾數是1 得 4個1

class Solution {
public:
    vector<int> countBits(int n) {
        //and[0] = 0;
        vector <int> ans(n+1,0);
        for(int i = 1; i <= n; i++){
            int temp = ans[i>>1];
            ans[i] = temp + ((i & 1) == 1 ? 1 : 0);
        }
        return ans;
    }
};