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

方法一：逐位判断

根据 与运算 定义，设二进制数字 $n$ ，则有：
- 若 $n & 1 = 0$ ，则 $n$ 二进制 最右一位 为 $0$ ；
- 若 $n & 1 = 1$ ，则 $n$ 二进制 最右一位 为 $1$ 。
根据以上特点，考虑以下 循环判断 ：
1. 判断 $n$ 最右一位是否为 $1$ ，根据结果计数。
2. 将 $n$ 右移一位（本题要求把数字 $n$ 看作无符号数，因此使用 无符号右移 操作）。

算法流程：

初始化数量统计变量 $res = 0$ 。
循环逐位判断：当 $n = 0$ 时跳出。
1. res += n & 1 ： 若 $n & 1 = 1$ ，则统计数 $res$ 加一。
2. n >>= 1 ： 将二进制数字 $n$ 无符号右移一位（ Java 中无符号右移为 "$>>>$" ）。
返回统计数量 $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$ 使用常数大小额外空间。

代码：

Python

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

Java

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

C++

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$ ，其余不变。

{:width=400}

算法流程：

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

<,,,>

复杂度分析：

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

代码：

Python

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

Java

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

C++

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