15 二进制中1的个数

Lin2J
2021-07-21 / 0 评论 / 85 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

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

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为 汉明重量).)。

解题思路:

首先介绍一个位操作,当 $n \neq 0$ 时,$n$ & $(n-1)$ 会消除掉 $n$ 最右边的 $1$,举个例子:

假设 $n = 1010$,则 $n - 1 = 1001$,$m = n$ & $(n -1 ) = 1000$,$m$ 和 $n$ 的对比之下,是否是 $n$ 最右边的 $1$ 变成了 $0$ 就是 $m$ 了。

$$ n = 1010 \\ m = 1000 $$

因此,每进行一次上述操作,$n$ 就会消掉一个 $1$,能进上多少次上述操作,说明 $n$ 就有多少个 $1$。

代码:

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

复杂度分析

  • 时间复杂度$O(N)$:$N$ 为 $n$ 的二进制 $1$ 的个数。

  • 空间复杂度$O(1)$: 变量 $c$ 使用常数大小额外空间。