LeetCode191——位1的个数(位运算)

2021-07-30  本文已影响0人  random_walk

位运算基础

位运算基于整数的二进制表示进行运算。由于计算机内部就是以二进制来存储数据,因此位运算会很快。基本的位运算共6种,分别为按位与、按位或、按位异或、按位取反、左移和右移。

与、或、异或

左移和右移

num << i 表示将 的二进制表示向左移动i位所得的值。
num >> i 表示将 的二进制表示向右移动 i位所得的值。
左移运算,右边全部补零。右移运算,如果是正数的话,左边全部补零,如果是复数的话补原始位。

位运算常见效果

image.png

题目描述

191. 位1的个数
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数。

方法一:循环检查

可以直接循环检查给定整数 n的二进制位的每一位是否为 1
代码:

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二:位运算优化

观察这个运算:n &(n - 1),其运算结果恰为把n的二进制位中的最低位的1变为 0之后的结果。n如果不为0,那么n-1就是二进制第一个为1的变为0,后面全为1

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


作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上一篇 下一篇

猜你喜欢

热点阅读