题目描述

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

https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

题解

循环检查二进制位

对 32位 int，循环检查二进制的每一位。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            if (n & (1 << i)) res++;
        }
        return res;
    }
};

时间复杂度： $O(k)$ ，该题 k = 32
空间复杂度： $O(1)$

位运算优化

n & (n - 1), 其结果为：把 n 最低位的 1 变为 0 的结果。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        for (; n; n &= (n - 1)) // n = n & (n - 1), 每次把 n 最低位的 1 变成 0
            res++;
        return res;
    }
};