剑指 Offer 15. 二进制中1的个数

题目链接：剑指 Offer 15. 二进制中1的个数

方法一：位运算

解题思路

x = n & -n，\(x\) 表示 \(n\) 的最后一位 \(1\) 所对应的值，每减去一次 \(x\)，相当于有一个 \(1\)，\(res ++\) 。

代码

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

复杂度分析

时间复杂度：\(O(logn)\)；
空间复杂度：\(O(1)\)。

方法二：循环取余

解题思路

通过 \(n\) 每次对 \(2\) 取余，若余 \(1\) 表示最后一位为 \(1\)，否则为 \(0\)，然后 \(n >> 1\)，继续上述操作。

代码

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n != 0) {
            res += n % 2;
            n /= 2;
        }
        return res;
    }
};

复杂度分析

时间复杂度：\(O(logn)\)；
空间复杂度：\(O(1)\)。