Counting Bits
題目描述
給定整數 n，回傳陣列 ans，其中 ans[i] 是 i 的二進位表示中 1 的個數（0 ≤ i ≤ n）。
輸入：n = 5
輸出：[0,1,1,2,1,2]
輸入：n = 2
輸出：[0,1,1]
解題思路
觀察規律
任何數字 i 右移一位後（i>>1）的 1 的個數已知，只需再看最低位是否為 1
DP 遞推
dp[i] = dp[i >> 1] + (i & 1)。例如 dp[5] = dp[2] + 1 = 2（5=101, 2=10）
從小到大填表
dp[0]=0 為 base case，i 從 1 到 n 遍歷，每個 dp[i] 只依賴 dp[i>>1]（更小的數字，已算過）
一次遍歷
每個 i 只做一次右移和一次 AND，O(n) 時間完成全部計算
程式碼
C#
public class Solution {
public int[] CountBits(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
// i >> 1 去掉最後一位，i & 1 取最後一位
dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}
}TypeScript
function countBits(n: number): number[] {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}Python
def countBits(n: int) -> list[int]:
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n) |
外層迴圈跑 n 次，每次只做一次右移和一次 AND 運算（O(1)），因此時間 O(n)。結果陣列本身就是 O(n) 空間，無額外空間開銷。
邊界情況
- n = 0：只有一個元素 dp[0] = 0，回傳
[0] - n = 1：回傳
[0, 1]，dp[1] = dp[0] + 1 = 1 - n 為 2 的冪次：例如 n = 8 (1000)，dp[8] = dp[4] + 0 = 1，2 的冪次只有 1 個 bit 為 1
圖解
圖表展示 dp[5] 的推導過程：5 的二進位是 101，右移一位得到 2（10），dp[2] 已知為 1。再加上 5 的最低位（5 & 1 = 1），得到 dp[5] = 1 + 1 = 2。
進階觀點
💡面試追問
-
Q: 還有其他遞推關係嗎？ A:
dp[i] = dp[i & (i-1)] + 1，其中i & (i-1)會去掉 i 最低位的 1。例如 dp[6] = dp[6&5] + 1 = dp[4] + 1 = 2。這個方法的直覺是：去掉一個 1 後的數字已經算過了，再加回那個 1。 -
Q: 不用 DP 的方法有哪些？ A:
__builtin_popcount（C++）、Integer.bitCount（Java）、bin(i).count('1')（Python）都可以直接數 1 的個數。但每個數字要花 O(log n) 時間逐 bit 處理，總時間 O(n log n)，不如 DP 的 O(n)。 -
Q: Brian Kernighan 演算法是什麼？ A:
while (n) { n &= n-1; count++; }— 每次n & (n-1)去掉最低位的 1，迴圈次數剛好等於 1 的個數 k。時間 O(k)，比逐 bit 掃描更快（k ≤ log n）。
理解測驗
🤔 dp[i] = dp[i >> 1] + (i & 1) 的直覺意義是什麼？
🤔 為什麼 i & (i-1) 可以去掉 i 最低位的 1？