题目描述

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

初始代码

class Solution {
public:
     int  NumberOf1(int n) {

     }
};

解法1

要输出2进制中的1的个数，由于已知二进制表示为32位，则只需要循环32次，验证数的每个位是否为1即可。

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0, i=0;
         while(i++ < 32)
         {
             if(n & 1) count++;
             n >>= 1;
         }
         return count;
     }
};

上述方法的时间复杂度为O(32), 空间复杂度为O(1)。

解法2

解法1无论输入的n值如何，都必须要循环32次才能得到结果。

而另一种思路，可以快速地定位到一个数从右向左数起的第一个1的位置.

假设n的二进制表示为11010010000，那么n-1的二进制表示为11010001111。两者做按位与运算，得到结果：11010000000。
这个做法的效果是，将n二进制表示中右边的第一个1变成了0。我们以此为依据，将要输出的计数结果加1。循环多次后，就可以统计出n中1的个数，并且不需要像解法1一样每次都必须得循环32次。

代码实现：

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;

         while(n != 0)
         {
             n = n & (n-1);
             count++;
         }
         return count;
     }
};