338. 比特位計數(shù)

給定一個非負整數(shù) num。對于 0 ≤ i ≤ num 范圍中的每個數(shù)字 i ，計算其二進制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。
示例 1:

輸入: 2
輸出: [0,1,1]

示例 2:

輸入: 5
輸出: [0,1,1,2,1,2]

題解

方法一：
Integer包裝類靜態(tài)方法：

    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = Integer.bitCount(i);
        }
        return res;
    }

方法二：動態(tài)規(guī)劃
1、i & (i - 1)可以去掉i最右邊的一個1（如果有），因此 i & (i - 1）是比 i 小的，而且i & (i - 1)的1的個數(shù)已經(jīng)在前面算過了，所以i的1的個數(shù)就是 i & (i - 1)的1的個數(shù)加上1

    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i < res.length; i++) {
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }

2、i >> 1會把最低位去掉，因此i >> 1 也是比i小的，同樣也是在前面的數(shù)組里算過。當 i 的最低位是0，則 i 中1的個數(shù)和i >> 1中1的個數(shù)相同；當i的最低位是1，i 中1的個數(shù)是 i >> 1中1的個數(shù)再加1

    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }