1. 位运算
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int hammingWeight(uint32_t n) {
int sum = 0;
for (int i = 0; i < 32; i++) {
sum += n & 1;
n >>= 1;
}
return sum;
}
};
|
2. 不修改n
方法1会修改n，且由于右移如果是负数，最高位补的是1，故不能写while(n)
方法2使用一个辅助变量，不是右移n，而是左移辅助变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int hammingWeight(uint32_t n) {
int sum = 0;
uint32_t f = 1;
while (f) {
if (n & f)
sum++;
f <<= 1;
}
return sum;
}
};
|
3. n & (n - 1)
上述两个方法的复杂度都是O(32)，需要遍历全部的32位。
考虑n-1，相比n，n中的最后一个1变成了0，右侧的0全部变成了1。
因此n & (n - 1)相当于把n最右侧的1去掉了，不论n是正还是负。
利用这个性质，可以在O(m)的时间内算出二进制中1的个数，m为二进制中1的个数，优于O(32)。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int hammingWeight(uint32_t n) {
int sum = 0;
while (n) {
n = n & (n - 1);
sum++;
}
return sum;
}
};
|