剑指 Offer 15. 二进制中1的个数

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

示例 1：

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

示例 2：

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

示例 3：

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

位运算

• 根据 与运算 定义，设二进制数字 nn ，则有：
  • 若 n & 1 = 0，则n二进制 最右一位 为 0；
  • 若 n & 1 = 1，则 n二进制 最右一位 为1 。
• 根据以上特点，考虑以下 循环判断 ：
  • 判断n最右一位是否为1，根据结果计数
  • 将n右移一位，(本题要求把数字n看作无符号数，因此使用无符号右移操作)

算法流程

• 初始化数量统计变量 res = 0
• 循环逐位判断：当n = 0时跳出
  • ​ res += n&1:若n&1 = 1，则统计数res加
  • n >>= 1 : 将二进制数字n无符号右移一位(java中无符号右移符号为 >>=)
• 返回res

AC代码

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}