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

题目描述
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

方法一：移位法求解

求解思路
对于二进制数要判断其中有多少个1，我们采用0x01这个数从右到左与n的每一位进行与操作来判断.

图片说明

解题代码

class Solution {
public:
     int  NumberOf1(int n) 
     {
        int myans = 0;
        int mymark = 0x01; // 进行与操作
        while (mymark != 0) 
        {
            if (mymark & n) ++myans; // 如果是1，ans+1
            mymark <<= 1;
        }
      return myans; // 返回结果
     }
};

复杂度分析
时间复杂度：因为是32位的二进制数，只循环依次，因此时间复杂度为 $O(1)$
空间复杂度：没有开辟新的地址内存空间，因此空间复杂度为 $O(1)$

方法二：优化的思想

求解思路
对于求解n中1的个数，我们可以让n和n-1进行与操作，这样每次进行与操作便可以消去一个1，直到最后n为0结束即可，用ans记录1的个数并输出ans。

图片说明

解题代码

class Solution {
public:
     int  NumberOf1(int n) 
     {
        int myans = 0;
        while (n != 0) // 结束条件
        {
            ++myans; // 记录n中1的个数
            n = n & (n-1); // 优化思想，让n与n-1进行与操作，这样便可以求出n中1的个数。
        }
        return myans; // 返回结果
     }
};

复杂度分析
时间复杂度：此种方法与n中1的个数有关，因此为 $O(N)$ ,N为二进制n中1的个数。
空间复杂度：没有引入新的地址空间，因此空间复杂度为 $O(1)$