请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
1、位运算
n：0101
1：0001
n&1：0001
可以知道最后一位是不是1，每次无符号移位前都做一次运算然后加起来，就能知道1的位数。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
//使用位运算
int res=0;
while(n!=0){
res+=n&1;
n>>>=1;
}
return res;
}
}
2、巧妙的位运算
n：0110
n-1：0101
n&(n-1)：0100
所以每次n&(n-1)可以消除n最右边的1。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
//使用位运算
int res=0;
while(n!=0){
n=n&(n-1);
res++;
}
return res;
}
}
3、Java源码
Integer中有一个方法bitCount()，能对1计数。
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}