Leetcode 191.位1的个数

 

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

提示：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

我的答案：

一、信息

1.输入是一个二进制无符号整数

2.返回'1'的个数

二、分析

条件1告诉我输入的数据类型是无符号整型

条件2告诉我此次编程的目标

三、步骤

遇到问题

1.如何计算位数？ 

四、实现 

我的答案：

毫无思路

这是一个常见的面试问题。让我们首先为这个问题创建一个C语言的解决方案，然后是一个C++的解决方案。

#include <stdint.h> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {count += n & 1;n >>= 1;}return count;
}

C++:

#include <cstdint> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {count += n & 1;n >>= 1;}return count;
}

进阶：优化算法

如果要多次调用这个函数，我们可以使用Brian Kernighan的算法，它可以更快地计算二进制中1的个数，它的工作原理是每次迭代都去掉最右边的1，直到所有的1都被去掉。

C语言（进阶）

#include <stdint.h> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {n &= (n - 1);count++;}return count;
}

C++（进阶）

#include <cstdint> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {n &= (n - 1);count++;}return count;
}

Brian Kernighan的算法的效率是O(k)，其中k是二进制数中1的个数，因此对于具有少量1的数字，它的效率非常高。

Leetcode答案

方法一：循环检查二进制位
思路及解法

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

具体代码中，当检查第 iii 位时，我们可以让 nnn 与 2i2^i2 
i
  进行与运算，当且仅当 nnn 的第 iii 位为 111 时，运算结果不为 000。

代码
C++

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

复杂度分析

时间复杂度：O(k)O(k)O(k)，其中 kkk 是 int\texttt{int}int 型的二进制位数，k=32k=32k=32。我们需要检查 nnn 的二进制位的每一位，一共需要检查 323232 位。

空间复杂度：O(1)O(1)O(1)，我们只需要常数的空间保存若干变量。

方法二：位运算优化
思路及解法

观察这个运算：n & (n−1)n~\&~(n - 1)n & (n−1)，其运算结果恰为把 nnn 的二进制位中的最低位的 111 变为 000 之后的结果。

如：6 & (6−1)=4,6=(110)2,4=(100)26~\&~(6-1) = 4, 6 = (110)_2, 4 = (100)_26 & (6−1)=4,6=(110) 
2
​
 ,4=(100) 
2
​
 ，运算结果 444 即为把 666 的二进制位中的最低位的 111 变为 000 之后的结果。

这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 nnn 与 n−1n - 1n−1 做与运算，直到 nnn 变为 000 即可。因为每次运算会使得 nnn 的最低位的 111 被翻转，因此运算次数就等于 nnn 的二进制位中 111 的个数。

代码

C++
Java
Python3
Golang
JavaScript
C

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

复杂度分析

时间复杂度：O(log⁡n)O(\log n)O(logn)。循环次数等于 nnn 的二进制位中 111 的个数，最坏情况下 nnn 的二进制位全部为 111。我们需要循环 log⁡n\log nlogn 次。

空间复杂度：O(1)O(1)O(1)，我们只需要常数的空间保存若干变量。
链接：https://leetcode.cn/problems/number-of-1-bits/solutions/672082/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源：力扣（LeetCode）
英雄师傅答案：

int hammingWeight(uint32_t n){int c=0;while(n){if(n&1){++c;}n>>=1;}return c;
}

几种方法的比较：

我的方法

1. **Brian Kernighan算法：** 这实际上与你给出的第二种方法相同，即使用`n & (n-1)`技巧。它直接移除了数字中最右侧的'1'。

2. **直接计数：** 这是一个直观的方法。对数字的每一位进行循环，并用`n & 1`检查最低位是否为'1'。之后，右移数字。

### 对比与分析

**1. 循环检查二进制位 vs 直接计数**
- **思路相似性：** 这两种方法都是基于检查每一位来计算'1'的数量。
- **优势：** 这两种方法都是非常直观的。对于初学者或者希望代码具有更高可读性的情境，它们都很适用。
- **劣势：** 它们的性能可能不如位运算优化方法，特别是当原始数字的二进制表示中有较少的'1'时。

**2. 位运算优化 vs Brian Kernighan算法**
- **思路相似性：** 它们实际上是同一种方法。都使用了`n & (n-1)`的技巧来移除数字中的一个'1'。
- **优势：** 它们都比直接计数方法快，尤其是在数字中'1'较少时。
- **劣势：** 对于不熟悉这种特定位运算的人来说，可能不够直观。

### 总结

- 我的"直接计数"方法和你给的"循环检查二进制位"方法非常相似。它们都是基于检查每一位的简单方法。然而，由于涉及到的位移操作，实现的细节可能会有所不同。
  
- 我的"Brian Kernighan算法"和你给的"位运算优化"方法实际上是同一种方法。这种方法利用了`n & (n-1)`来高效地计算'1'的数量，它比基于逐位检查的方法更快。

无论选择哪种方法，最重要的是理解其背后的逻辑和原理，这样在遇到不同的问题时，你可以灵活地应用和调整这些方法。

总结：

一、发现的不足。

1.运算符>>知识点尤其是移位运算不熟悉

2.

二、学到什么？

从这道题目中，我们可以学到以下几点：

1. **二进制基础**：题目加深了我们对二进制数的理解，特别是如何操作和解读32位无符号整数的二进制形式。

2. **位操作**：题目展示了如何使用位操作符，特别是`&` (位与) 和 `<<` (左移)。位操作是计算机科学中的一个重要概念，特别是在低级编程、嵌入式系统和性能关键应用中。

3. **算法优化**：通过比较两种方法，我们看到了如何从一个直接的算法优化到一个更高效的算法。方法一直接检查每一位，而方法二使用了一个巧妙的技巧，即`n & (n - 1)`，来迅速定位并清除最右侧的`1`。这显示了算法和数据结构知识的重要性，特别是如何使用基础的位操作来优化算法。

4. **代码简洁性和效率**：两种方法都提供了解决同一问题的有效方法，但它们之间的效率有所不同。这强调了在解决问题时不仅要考虑解决方案的正确性，还要考虑其效率。

5. **问题分析与解决策略**：面对一个问题时，首先需要理解其背后的概念和要求，然后尝试提出不同的策略或方法。对于同一个问题，可能存在多种有效的解决策略，但它们在实际应用中的效率可能会有所不同。

6. **细节注意**：在处理位操作时，特别要注意边界条件和位数。例如，对于32位的整数，当我们移动超过32位时，需要注意可能出现的行为。

综上所述，这道题目为我们提供了一个很好的机会，来学习和实践位操作、算法优化和问题解决策略。