Skip to content
当前页大纲

方法一:逐位判断

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

<Picture2.png,Picture3.png,Picture4.png,Picture5.png,Picture6.png,Picture7.png,Picture8.png,Picture9.png,Picture10.png>

代码:

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

复杂度分析:

  • 时间复杂度 $O(\log 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$ ,其余不变。

Picture1.png

算法流程:

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

<Picture11.png,Picture12.png,Picture13.png,Picture14.png>

代码:

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

复杂度分析:

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

MIT License.