编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '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$ 使用常数大小额外空间。
评论区