tags： 位运算
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
样例输入
3 4 5 -1
样例输出
1 2 3 2
参考
我们很容易想到的算法就是
通过移位的方法，挨个判断其每一位
class Solution
{
public:
int NumberOf1(int n)
{
int count = 0;
while(n)
{
if(n & 1 == 1)
{
count++;
}
n >>= 1;
}
return count;
}
};但是这个算法有致命的缺陷，我们假设通过移位的方式可以获取到其每一位，但是并不总是对的. 这是由于右移的特点决定的
左移运算符m<<n表示把m左移n位. 在左移n位的时候, 最左边的n位将被丢弃, 同时在最右边补上n个0. 比如
00001010<<2=00101000
10001010<<3=01010000
右移运算符m>>n表示把m右移n位. 在右移n位的时候, 最右边的n位被丢弃, 但是在处理最左边的情形要复杂一些. 如果数字为无符号数, 则用0补上最左边的n位. 如果数字是有符号数要分情况, 如果为正数, 则用0补上, 如果是负数, 就用1补上. 下面是两个8位有符号数右移的例子
00001010>>2=00000010
10001010>>3=11110001
所以上面用右移的解法存在的问题是, 如果输入是负数, 右移后最高位会被设为1, 如果一直做右移运算, 数字永远不会为0, 陷入死循环.
为了负数时候避免死循环，我们可以不右移数字n，转而去移动测试位
class Solution
{
public:
int NumberOf1(int n)
{
int count = 0;
unsigned int flag = 1;
while(flag != 0)
{
if((n & flag) != 0)
{
count++;
}
flag <<= 1;
}
return count;
}
};这种方法循环的次数正好是是整数二进制数的位数，比如int就是32位循环32次
那么有没有一种方法，整数中有几个1就循环几次呢？
我们分析n以n-1两个数的差别，
- 如果n!=0，那么其二进制位中至少有一个1
- 如果n的最低位是1（奇数），那么n-1正好把这个最低位的1变成0，其他位不变
- 如果n的最低位是0（偶数），那么假设其右起第一个1位于m位，即m位后面全是0，那么n-1的第m位由1变成0，而第m位后面的所有0均变成1，m位之前的所有位保持不变。
因此通过分析发现：
把一个整数n减去1，再和原来的整数做与运算，会把该整数最右边一个1变成0，那么该整数有多少个1，就会进行多少次与运算
即循环的次数，即二进制中1的个数
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
class Solution {
public:
int NumberOf1(int n) {
int count=0;
while(n){
count++;
n=(n-1)&n;
}
return count;
}
};但是这个算法有致命的缺陷，我们假设通过移位的方式可以获取到其每一位，但是并不总是对的