题目
题目链接
题目的主要信息：
统计32位整型有符号数二进制中1的个数
因负数用补码表示，故不能用连除法
举一反三：
学习完本题的思路你可以解决如下题目：
JZ64. 求1+2+3+...+n
JZ65. 不用加减乘除做加法
方法一：循环按位比较法（推荐使用）
知识点：位运算
计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。
思路：
我们可以检查该数字的二进制每一位是否为1，如果遍历二进制每一位呢？可以考虑移位运算，每次移动一位就可以。至于怎么统计到1呢？我们都只知道数字1与数字相位与运算，其实只是最后一位为1就是1，最后一位为0就是0，这样我们只需要将数字1移位运算，就可以遍历二进制的每一位，再去做位与运算，结果为1的就是二进制中为1的。
具体做法：
step 1：遍历二进制的32位，通过移位0-31次实现。
step 2：将移位后的1与数字进行位与运算，结果为1就记录一次。
Java实现代码：
public class Solution {
public int NumberOf1(int n) {
int res = 0;
//遍历32位
for(int i = 0; i < 32; i++){
//按位比较
if((n & (1 << i)) != 0)
res++;
}
return res;
}
}
C++实现代码：
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
//遍历32位
for(int i = 0; i < 32; i++){
//按位比较
if((n & (1 << i)) != 0)
res++;
}
return res;
}
};
Python实现代码：
class Solution:
def NumberOf1(self , n: int) -> int:
res = 0
#遍历32位
for i in range(32):
#按位比较
if (n & (1 << i)) != 0:
res += 1
return res
复杂度分析：
时间复杂度：\(O(k)\)，\(k\)为int型的32位，一次遍历
空间复杂度：\(O(1)\)，常数级变量，没有额外辅助空间
方法二：位运算优化法（扩展思路）
思路：
有一个性质：\(n\&(n-1)\)，会将n的二进制中最低位由1变成0
我们可以不断让当前的 \(n\)与 \(n - 1\)做位与运算，直到 \(n\)的二进制全部变为 0 停止。因为每次运算会使得 \(n\) 的最低位的 1 被翻转成0，因此运算次数就等于 \(n\) 的二进制位中 1 的个数，由此统计1的个数。
具体做法：
step 1：使用循环检查\(n\)是否为0.
step 2：不为0就与\(n-1\)做位与运算，去掉二进制最后一位的1，并统计次数。
图示：
Java实现代码：
public class Solution {
public int NumberOf1(int n) {
int res = 0;
//当n为0时停止比较
while(n != 0){
n &= n - 1;
res++;
}
return res;
}
}
C++实现代码：
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
//当n为0时停止比较
while(n){
n &= n - 1;
res++;
}
return res;
}
};
Python实现代码：
class Solution:
def NumberOf1(self , n: int) -> int:
res = 0
#负数转换
if n < 0:
n &= 0xffffffff
#当n为0时停止比较
while n:
n &= n - 1
res += 1
return res
复杂度分析：
时间复杂度：\(O(log_2n)\)，\(n\)为数字的大小，循环次数等于\(n\)的二进制位中1的个数，最坏情况下\(n\)的二进制位全部为1，也即开一个2的log运算
空间复杂度：\(O(1)\)，常数级变量，没有额外辅助空间