吴江区建设工程招标网站,注册安全工程师报名时间2022官网,开公司一年需要多少费用,手机做的兼职网站编写一个函数#xff0c;输入是一个无符号整数#xff08;以二进制串的形式#xff09;#xff0c;返回其二进制表达式中数字位数为 1 的个数#xff08;也被称为汉明重量#xff09;。 提示#xff1a;
请注意#xff0c;在某些语言#xff08;如 Java#xff09;中… 编写一个函数输入是一个无符号整数以二进制串的形式返回其二进制表达式中数字位数为 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 型的二进制位数k32k32k32。我们需要检查 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 c0;while(n){if(n1){c;}n1;}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位时需要注意可能出现的行为。
综上所述这道题目为我们提供了一个很好的机会来学习和实践位操作、算法优化和问题解决策略。
