題目
#

題目簡述
#

計算從 0 到 n 的每個數字的二進制表示中 ‘1’ 的個數。

範例
#

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation: 
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation: 
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

解題思路
#

這題要求我們計算從 0 到 n 的每個數字的二進制表示中 ‘1’ 的個數。我們可以使用位運算來逐位檢查每個數字的 ‘1’ 的個數，並將結果存儲在一個陣列中。

解法
#

位運算計數法（Bit Manipulation Counting Approach）

初始化結果陣列 res，大小為 n+1
遍歷從 0 到 n 的每個數字：
- 對於每個數字，使用位運算計算 ‘1’ 的個數
- 將計算結果存入 res 陣列
返回結果陣列 res

步驟
#

初始化：
- 創建結果陣列 res，大小為 n+1
計算位數：
- 遍歷從 0 到 n 的每個數字
- 使用位運算計算 ‘1’ 的個數
- 將結果存入 res 陣列
返回結果：
- 返回 res 陣列

例子說明
#

n = 5

數字	二進制	‘1’ 的個數
0	0	0
1	1	1
2	10	1
3	11	2
4	100	1
5	101	2

完整程式碼
#

java

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];

        // 遍歷從 0 到 n 的每個數字
        for(int i = 0; i <= n; i++){
            int k = i;
            int cnt = 0;
            // 使用位運算計算 '1' 的個數
            while(k > 0){
                cnt += k & 1;
                k >>= 1;
            }
            // 將結果存入 res 陣列
            res[i] = cnt;
        }

        // 返回結果陣列
        return res;
    }
}