题目描述

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

二进制位运算

二进制位运算只有5种：与、或、异或、左移、右移
与：&
或：|
异或：^
左移：<<
例：m<<n表示把m左移n位，在左移n位时，最左边的n位会被丢弃，同时在最右边补上n个0
右移：>>
例：m>>n表示把m右移n位，在右移n位时，最右边的n位会被丢弃。但是右移时处理最左边位的情形要稍微复杂一些，如果数字是一个无符号数值，则用0填补最左边的n位，如果数字是个有符号数值，则用数字的符号位填补最左边的n位。也就是说，如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补上n个1。
00001010>>2=00000010
10001010>>3=11110001

思路

(1)思路1
先判断整数二进制表示最右边一位是不是1——将整数与1做与运算，若为0，则最右不是1，若为1，则最右为1；
然后把整数右移一位，再判断是不是1；
直到整数变为0；
但是这种解***造成死循环，因为如果整数是一个负数，右移1位填补左边时填补符号位1，那么最后会变成0xFFFFFFFF而陷入死循环

（2）思路2
首先把n和1做与运算，判断n的最低位是否为1；
然后把1左移一位，再与n做与运算，判断n的次低位是否为1；
循环次数等于整数二进制的位数，32位的整数需要循环32次,

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

(3)思路3
首先分析一下一个数减去1的情况
假设这个数的最右边一位为1，减去1时，最后一位变成0其他所有位保持不变；
假设这个数的最右边一位为0，减去1时，从右往左第一个1变为0，它右边的0全都变为1，左边不变。
1100-1=1011
归纳：一个整数减去1，都是把最右边的1变为0，如果它的右边还有0，则所有0变为1，左边所有位保持不变
然后将这个整数和减去1进行与运算——相当于把最右边的1变为0
1100&1011=1000

回到题目中，也就是说，一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作

class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         while(n)
         {
             count++;
             n=(n-1)&n;
         }
         return count;
     }
};