题目

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
     int  NumberOf1(int n) {
         int count =0;
         int flag =1;
         while(flag)
         {
             if(n&flag) count++;
             flag =flag<<1;
         }
         return count;
     }
};

思路

二进制的位运算一共有5种运算，与，或，异或，左移，右移。

左移运算符m<<n表示把m左移n位，在左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。例如

1
2
00001010 << 2 = 00101000
10001010 << 3 = 01010000

右移运算符表示把m右移n位，在右移n位的时候，最右边的n位将被丢弃，同时右移稍微复杂一点，如果数字是一个无符号数值，则用0填补最左边的n位，如果数字是一个有符号数值，则用数字的符号位填补最左边的n位，也就是说，正数右移左边补0，负数右移左边补1.

回到此题，基本的思路就是让1与每一位异或，如果答案是0，说明原来也是1，这里就出现一个问题，怎么移动位置，可以移动原来的数字，也可以移动1，但是移动原来的数字时，当是负数的时候，因为最高位补1，所以可能会产生死循环，所以应该把1不断的左移。