方法一：逐位判断 ​

• 根据 与运算 定义，设二进制数字 $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$ 。

<,,,,,,,,>

复杂度分析： ​

• 时间复杂度 $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$ 使用常数大小额外空间。

代码： ​

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;
    }
};

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

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

算法流程： ​

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

<,,,>

复杂度分析： ​

• 时间复杂度 $O(M)$ ： $n & (n - 1)$ 操作仅有减法和与运算，占用 $O(1)$ ；设 $M$ 为二进制数字 $n$ 中 $1$ 的个数，则需循环 $M$ 次（每轮消去一个 $1$ ），占用 $O(M)$ 。
• 空间复杂度 $O(1)$ ： 变量 $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;
    }
};