xiaoyu

题目描述

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

可能引起死循环的解法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
while (n) {
if (n & 1) cnt++;
n >>= 1;
}
return cnt;
}
};

由于数字在计算机中的二进制存储事实上并不包含符号(也就是+-),都是统一用补码表示的。
移位操作会保证数的正负不变,当遇到一个负数,右移到最前面的符号位1时,再往右移并不会变成期待的0,最高位永远保持为1,这就会死循环。

改进(非通用)

我们假定这里的整数就是占32位,那么就可以固定住枚举次数,但是不一定通用(实际上我们是假设这个整数就是32位二进制存储的)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
for (int i = 0; i < 32; i++) {
if (n >> i & 1) cnt++;
}
return cnt;
}
};

一般解法:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
unsigned flag = 1;
while (flag) {
if (n & flag) cnt++;
flag <<= 1;
}
return cnt;
}
};

最优解法

这个方法的好处在于,有多少个1就只需要循环多少次

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
while (n) {
cnt++;
n = n & (n - 1); // n & (n - 1)的作用相当于将这个数的最后一个1变成0
}
return cnt;
}
};

 评论