题目描述
输入一个整数，输出该数二进制表示中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);
}
return cnt;
}
};
|