编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '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(logn)O(\log n)O(logn)。循环次数等于 nnn 的二进制位中 111 的个数,最坏情况下 nnn 的二进制位全部为 111。我们需要循环 logn\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位时,需要注意可能出现的行为。
综上所述,这道题目为我们提供了一个很好的机会,来学习和实践位操作、算法优化和问题解决策略。