二进制中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;
}
