剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int highBit = 0;
        for(int i = 1; i < n + 1; i++) {
            // ans[i] = Integer.bitCount(i);
            // ans[i] = bit1(i);
            // ans[i] = bit2(i);
            ans[i] = ans[i & (i - 1)] + 1;
            // ans[i] = ans[i >> 1] + (i & 1); // 最低位 1，右移分奇偶。
            // 记录 i 的最高 bit 位。最高位 1
            // if ((i & (i - 1)) == 0) highBit = i; 
            // ans[i] = ans[i - highBit] + 1;
        }
        return ans;
    }

    int bit1(int x){
        int res = 0;
        while(x > 0){
            res += x % 2; x /= 2;
        }
        return res;
    }
    
    int bit2(int x){
        int res = 0;
        while(x > 0){
            x &= x - 1; res++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33