二进制中1的个数

问题陈述

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

方法一：逐位与1相与

根据 与运算 定义，设二进制数字 n ，则有：
若 n & 1 = 0，则 n 二进制 最右一位 为 0 ；
若 n & 1 = 1 ，则 n 二进制 最右一位 为 1。

根据以上特点，考虑以下 循环判断 ：
判断 n 最右一位是否为 1 ，根据结果计数。
将 n右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）。

1
2
3
4
5
6
7
8
class Solution{
    int res=0;
    while(n!=0){//当全部比较完，n的二进制位全为0，即n=0.
        res+=n&1;
        n>>>=1;//java无符号右移，这样每次将n的二进制位置于最尾进行比较。
    }
}

二进制移位相关知识

  • **无符号右移：**无论是正数还是负数，高位通通补0。
  • 右移运算符：它表示是将运算符左边的对象向右移动，移动位数为运算符右边指定的数，并且在高位补0，其实右移n位，就相当于除于2的n次方。
  • 带符号右移运算符：它表示将运算符左边的运算对象，向右移动运算符右边指定的位数。如果是正数，在高位补零，如果是负数，则在高位补1；
  • **左移运算符：**它表示是将运算符左边的对象，向左移动运算符右边指定的位数，并且在低位补零。其实，向左移n位，就相当于乘上2的n此方；

方法二：n &（n-1）

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res++;
            n &= n - 1;//消去数字 n 最右边的 1 。
        }
        return res;
    }
}