思路：
题目的主要信息：
- 统计32位整型有符号数二进制中1的个数
- 因负数用补码表示，故不能用连除法
方法一：循环按位比较法
具体做法：
可以直接循环检查二进制的每一位是否为1.
- 1 << i： 用于移位
- & ：与运算比较是否为1
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) { //按位比较
res++;
}
}
return res;
}
};复杂度分析：
- 时间复杂度：
，k为int型的32位，一次遍历
- 空间复杂度：
，没有额外空间
方法二：位运算优化法
具体做法：
有一个性质：n&(n-1)，会将n的二进制中最低位由1变成0
我们可以不断让当前的 n与 n - 1做与运算，直到 n 变为 0 停止。因为每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数，由此统计1的个数。
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
while (n) { //当n为0时停止比较
n &= n - 1;
res++;
}
return res;
}
};复杂度分析：
- 时间复杂度：
，n为数字的大小，循环次数等于n的二进制位中1的个数，最坏情况下n的二进制位全部为1，也即开一个2的log运算
- 空间复杂度：
京公网安备 11010502036488号