二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 **00000000000000000000000000001011** 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'

方法一：逐位判断

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        if ((n & 1) != 0) {
            count++;
        }
        n >>>= 1;
    }
    return count;
}

方法二：计1的个数

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count++;
        n = n & (n - 1);
    }
    return count;
}

比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num范围中的每个数字 i，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

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

示例 2:

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

方法一：每次计算每个数的二进制1的个数

public int[] countBits(int num) {
    int[] ans = new int[num + 1];
    for (int i = 0; i <= num; i++) {
        ans[i] = popCount(i);
    }
    return ans;
}

public int popCount(int x) {
    int ans = 0;
    while (x != 0) {
        x &= x - 1;
        ans++;
    }
    return ans;
}

方法二：动态规划+最低有效位

比如   2    10
       4    100
       5    101
4的二进制1的个数等于2的，因为右移一位，移除了0,1的个数没有变
5的二进制1的个数等于2的+1，因为右移一位，移除了1,1的个数少了一个

P(x)=P(x/2)+(xmod2)

public int[] countBits(int num) {
    int[] ans = new int[num + 1];
    for (int i = 1; i <= num; i++) {
        ans[i] = ans[i / 2] + i % 2;
    }
    return ans;
}