LeetCode191——位1的个数（位运算）

位运算基础

位运算基于整数的二进制表示进行运算。由于计算机内部就是以二进制来存储数据，因此位运算会很快。基本的位运算共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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。