leetcode.191. 位1的个数

淩亂°似流年 2022-11-14 13:19 131阅读 0赞

# [191. 位1的个数][191. _1] #

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

**提示：**

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

**提示：**

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

# 思路与代码 #

方法一，

我们可以直接循环检查给定整数 `n` 的二进制位的每一位是否为 1。

具体代码中，当检查第 `i` 位时，我们可以让 `n`与 `2^i`进行与运算，当且仅当 `n` 的第 `i`位为 1 时，运算结果不为 0。

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

方法二，

有个更为神奇的做法，那就是 `n & (n - 1)` ，这个代码可以把 n 的二进制中，最后一个出现的 1 改写成 0。

下面的这个图，说明了 `n & (n - 1)`这个操作的原理。我们发现只要每次执行这个操作，就会消除掉 `n` 的二进制中 最后一个出现的 1。

因此执行 `n & (n - 1)` 使得 n 变成 0 的操作次数，就是 n 的二进制中 1 的个数。

![在这里插入图片描述][f8e3aca1a1a6819360c74741222f8bdf.png_pic_center]

代码

class Solution { 
    public:
        int hammingWeight(uint32_t n) { 
            int ret = 0;
            while (n) { 
                n &= n - 1;
                ret++;
            }
            return ret;
        }
    };

[191. _1]: https://leetcode-cn.com/problems/number-of-1-bits/
[Link 1]: https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E8%BF%9B%E5%88%B6%E8%A1%A5%E7%A0%81/5295284
[f8e3aca1a1a6819360c74741222f8bdf.png_pic_center]: /images/20221022/95be3e89b60e4912940ee78f26d47837.png