题目的主要信息:
  • 统计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)O(k)kk为int型的32位,一次遍历
  • 空间复杂度:O(1)O(1),常数级变量,没有额外辅助空间
方法二:位运算优化法(扩展思路)

思路:

有一个性质:n&(n1)n\&(n-1),会将n的二进制中最低位由1变成0

我们可以不断让当前的 nnn1n - 1做位与运算,直到 nn的二进制全部变为 0 停止。因为每次运算会使得 nn 的最低位的 1 被翻转成0,因此运算次数就等于 nn 的二进制位中 1 的个数,由此统计1的个数。

具体做法:

  • step 1:使用循环检查nn是否为0.
  • step 2:不为0就与n1n-1做位与运算,去掉二进制最后一位的1,并统计次数。

图示:

alt

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(log2n)O(log_2n)nn为数字的大小,循环次数等于nn的二进制位中1的个数,最坏情况下nn的二进制位全部为1,也即开一个2的log运算
  • 空间复杂度:O(1)O(1),常数级变量,没有额外辅助空间