[Lc]191位1的个数

题目

题解

1. 位掩码

设置一个位掩码mask，初值为1，每次1向左移动一位，mask与n做与运算之后只有mask中为1的那一位为保留，其余归0。因此若结果不为0则停机位数的结果++

• 时间复杂度$O(1)$，最多循环32次
• 空间复杂度$O(1)$

class Solution {//两个方法。1. 位掩码
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        uint32_t mask = 1;
        for(int i=0; i<32; ++i){
            if((mask&n) != 0) res++;
            mask <<= 1;
        }
        return res;
    }
};

2. 与n-1与

这是一个二进制数的小技巧。当n不为0的时候，用n&n-1，则会把n的最后一位1变为0，用这个性质写的代码十分简洁。

• 时间复杂度$O(1)$，最多循环32次
• 空间复杂度$O(1)$

class Solution {//两个方法。2. 与n-1与
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n != 0){
            res++;
            n &= n-1;
        }
    return res;
    }
};