LeetCode 191 Number of 1 Bits

位1的个数

题意

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 1 的个数.

示例 1:

1
2
3
输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

1
2
3
输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

1
2
3
输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

解法一

这里用到了位运算, 如数字 5, 二进制位为 101, 那么使用 & 运算, 和 1 进行与运算, 如:

1
2
3
4
  101
& 001
-----
001

因为 1 只有最后一位为 1, 其他为都是 0, 所以他与任何数进行 & 运算后, 都只会保留这个数的最后一位, 如果运算结果还是 1, 说明这个树的最后一位是 1, 反之为 0.

那就很好解决了, 将 num & 1 后判断为 1, 则计数增加 1, 然后将右移一位 num >>= 1, 以此类推, 直到移位 32 次.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
n >>= 1;
}
return bits;
}
}

时间复杂度 O(1), 空间复杂度 O(1).

解法二

这个解法有些取巧, 在二进制表示中,数字 n 中最低位的 1 总是对应 n - 1 中的 0. 因此, 将 nn - 1 与运算总是能把 n 中最低位的 1 变成 0, 并保持其他位不变.

如对于数字 10, 和 10 - 1 进行 & 运算:

1
2
3
4
  1010
& 1001
------
1000

接着对于二进制值 1000, 与 999 进行 & 运算:

1
2
3
4
  1000
& 999
------
0000

由于每次都把最低位的 1 变为 0 了, 直到为 0, 那么这种个编程变了几次就说明有多少个 1.

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int hammingWeight(int n) {
int sum = 0;
while (n != 0) {
sum++;
n &= (n - 1);
}
return sum;
}
}

时间复杂度 O(1), 空间复杂度 O(1). 但此算法效率相对比算法一效率高.