15 二进制中1的个数

剑指 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$ 就会消掉一个 $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$ 使用常数大小额外空间。