《剑指offer》 第15题 二进制中1的个数

和1 与 为1，则为1，否则为0，因此用 与 操作来判断是否为1

思路1：
首先应该想到的是，先判断最右边的是否为1，然后整体右移一位，这样原来右边第二个数就被移动到最右边了，再判断；反复这样，就可以得到1的个数。
关键是这样的想法，在进行负数的个数统计时，会有问题，因为负数的二进制首位为1，移位后，为了保证还是负数，计算机会在首位再补1，这样不管你怎么移动，首位永远是1，陷入死循环。因此需要转变思路。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                count++;
            }

            n = n >> 1;//把n的2进制形式往右推一位
        }
        return count;
    }
}

思路2：基于思路1的改进，既然原来的数右移可能会出问题，那就不移位。那原来的数不右移了，我用另一个数左移来相 与（相对运动可还行）。
flag 变化是 1 10 100 1000 ...
直到变成1000000..... 最终计算机认为你的首位是负数的标志时，再移动一次后，就全变成了0。此时为循环终止条件
那么代码如下

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        int flag = 1;
        while(flag != 0){
            if((n & flag) != 0){ //flag只有首位是1，其余位是0，相与为0，说明比较的当前位是0
                count ++;
            }
            flag = flag << 1;
        }
        return count;
    }
}

思路3：一个数的二进制减1后，原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 如1100 减1 变 1011。两数相与是1000,则这样的一次操作去掉了最右边的1（1100百位的1没了），利用这个规律进行解题。

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