咸鱼回响

望之天回,即之云昏

0%

【剑指 offer】15.二进制中1的个数

发表于 更新于

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof

题目描述

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 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'。

提示：

  • 输入必须是长度为 32 的 二进制串 。

    我的解题

    思路

    通过逐位比较来确定给定数字中出现的1的个数，这里我一开始使用了取模，实际上还有更快的位运算，不过这里有个小坑，即题目中给定的int需要看成无符号位，即当int为负数的时候最高位是1。因此需要在Java中通过>>>来达成数字的无符号移动。

结果

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int size = 0;
        while (n != 0) {
            size += (n & 1);
            n >>>= 1;
        }
        return size;
    }
}

最优解

思路

有两种方法，一种就是上面的通过每一位的比较来得到数字中1的个数，但是还有一个更快的方法，即通过n&(n-1)这样的位运算。n-1在二进制中表示将n的最低位的1修改成0。与上面方法的区别就是，逐位计算循环次数固定是数字的位数，这种方法的循环次数则是数字中1的个数。设上一种方法的时间复杂度为O(N)、这种时间复杂度为O(M)，则N >= M.

解法

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int size = 0;
        while (n != 0) {
            size += 1;
            n = n & (n - 1);
        }
        return size;
    }
}