LeetCode–二进制中1的个数

归子莫

发布于：2020年9月5日

LeetCode–二进制中1的个数

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

介绍

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

主站 191

题目

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

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

思路

作者：jyd

逐位判断

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

步骤

初始化数量统计变量 res =0 。
循环逐位判断：当 n =0 时跳出。
- res += n & 1 ：若 n & 1 = 1n&1=1 ，则统计数 resres 加一。
- n >>= 1 ：将二进制数字 nn 无符号右移一位（ Java 中无符号右移为 “>>>” ）。
返回统计数量 res

皮一下

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

代码

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;
    }
}