LeetCode-Book/leetbook_ioa/docs/LCR 133. 位 1 的个数.md

方法一：逐位判断

根据 与运算 定义，设二进制数字 n ，则有：

• 若 n \& 1 = 0 ，则 n 二进制 最右一位 为 0 ；
• 若 n \& 1 = 1 ，则 n 二进制 最右一位 为 1 。

根据以上特点，考虑以下 循环判断 ：

1. 判断 n 最右一位是否为 1 ，根据结果计数。
2. 将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）。

算法流程：

1. 初始化数量统计变量 res = 0 。
2. 循环逐位判断： 当 n = 0 时跳出。
   1. res += n & 1 ： 若 n \& 1 = 1 ，则统计数 res 加一。
   2. n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 "$>>>$" ） 。
3. 返回统计数量 res 。

<,,,,,,,,>

代码：

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n & 1
            n >>= 1
        return res

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int res = 0; // c++ 使用无符号数
        while(n != 0) {
            res += n & 1;
            n >>= 1;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度 O(\log_2 n) ： 此算法循环内部仅有 移位、与、加 等基本运算，占用 O(1) ；逐位判断需循环 log_2 n 次，其中 \log_2 n 代表数字 n 最高位 1 的所在位数（例如 \log_2 4 = 2, $\log_2 16 = 4$）。
• 空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。

方法二：巧用 n \& (n - 1)

• (n - 1) 解析： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
• n \& (n - 1) 解析： 二进制数字 n 最右边的 1 变成 0 ，其余不变。

{:align=center width=450}

算法流程：

1. 初始化数量统计变量 res 。
2. 循环消去最右边的 1 ：当 n = 0 时跳出。
   1. res += 1 ： 统计变量加 1 ；
   2. n &= n - 1 ： 消去数字 n 最右边的 1 。
3. 返回统计数量 res 。

<,,,>

代码：

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

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

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

复杂度分析：

• 时间复杂度 O(M) ： n \& (n - 1) 操作仅有减法和与运算，占用 O(1) ；设 M 为二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个 1 ），占用 O(M) 。
• 空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。