☆打卡算法☆LeetCode 191. 位1的个数 算法解析

一、题目

1、算法题目

“编写一个函数，输入是无符号整数，返回其二进制表达式中数字位数为1的个数。”

题目链接：

来源：力扣（LeetCode）

链接： 191. 位1的个数 - 力扣（LeetCode）

2、题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

  提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。

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

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

二、解题

1、思路分析

这道题是要我们求出二进制串中数字位数为1的个数。

可以遍历枚举出给定二进制串中的每一位是否为1。

在实际代码中，当检查到i位的时候，可以让n与2i进行与运算，当且n的第i位为1时，运算结果不为0。

2、代码实现

代码参考：

public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((n &amp; (1 << i)) != 0) {
                ret++;
            }
        }
        return ret;
    }
}

3、时间复杂度

时间复杂度：O(k)

其中k是int型的二进制位数，k=32。

需要检查n的二进制位的每一位，一共是32位。

空间复杂度：O(1)

只需要常量级的变量空间。

三、总结

在实现代码的过程中使用了一个与运算，判断 第i位的2i末尾是否为1。

也可以利用这个运算的性质优化代码。

比如让当前n与n-1做与运算，直到n变为0即可。