剑指Offer第15题——二进制中1的个数

实现一个函数，输入一个整数，输出该数二进制表示中1的个数。

右移版本

public int numberOf1_2(int n) {
    int count = 0;

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

注意：右移必须要用>>>,而不能用普通的>>。原因是因为>>为带符号的右移，对于负数来说高位会以1来补位，导致高位无限为1，会出现无线循环。
所以要使用无符号右移。>>> 为无符号右移，无论正负数，都在高位补0。
左移版本
用一个1和输入数的每一位相与，然后将这个1不断左移。

public int numberOf1_1(int n) {
    int count = 0;
    int flag = 1;
    while (flag != 0) {
        if ((n & flag)!= 0) {
        count++;
        }
        // 每次改变的只是这个变量，输入的数始终没有被改变过
        flag = flag << 1;
    }
    return count;
}

总结
左移一位，相当于原数 * 2，左移两位，相当于原数 * 4
右移一位，相当于 原数 / 2，右移两位，相当于 原数 / 4