题解 | #二进制中1的个数#

思路：

题目的主要信息：

• 统计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运算
• 空间复杂度：，没有额外空间