191. 位 1 的个数 ●

191. 位 1 的个数 ●

描述

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

示例

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

题解

1. 循环检查二进制位

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

具体的，从二进制数低位到高位进行检查，每次移动 $i-1$ 位，并与 $1$ 做 & 与运算，来检查第 $i$ 低位的数，

• 时间复杂度：$O(k)$，其中 k 是 int 型的二进制位数，$k=32$。我们需要检查 n 的二进制位的每一位，一共需要检查 32 位。
• 空间复杂度：$O(1)$，我们只需要常数的空间保存若干变量。

class Solution {
public:int hammingWeight(uint32_t n) {int ans = 0;for(int i = 0; i < 32; ++i){if(n & 1){++ans;		// 位移后，最低位为 1 时，则ans++}n >>= 1; }return ans;}
};

2. 位运算优化

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

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

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

• 时间复杂度：$O(\log n)$。循环次数等于 n 的二进制位中 1 的个数，最坏情况下 n 的二进制位全部为 1。
• 空间复杂度：$O(1)$，我们只需要常数的空间保存若干变量。

class Solution {
public:int hammingWeight(uint32_t n) {int ans = 0;while(n){           // 还存在 1++ans;n &= n - 1;     // 该操作后，最低位的 1 将被翻转为 0}return ans;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！