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

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

解法1

方式很简单，但是没有通过AC，在例子input=-2147483648的时候报错
原理是，取这个数字的模，如果为1 这个数字一定是奇数，那这个数字的二进制最后一位一定是1，

   public int NumberOf1(int n) {
        int res = 0;
        long input = Math.abs(n);
        while (input != 0) {
            if (input % 2 == 1) {
                res++;
            }
            input = input / 2;
        }
        return res;
    }

解法2

求二进制中1的个数，那么就对于原来数字中的每一位，用与运算判断是不是1，这里用了一个flag，这个flag从1开始，每次左移一位，与输入的int做与运算，如果发现是1，则表明原int在此时对应的位上是1

public int NumberOf1_2(int n) {
        int flag = 1;
        int res = 0;
        while (flag != 0) {
            if ((n & flag) != 0) {
                res++;
            }
            flag = flag << 1;
        }
        return res;
    }

解法3

n & n-1这个运算符，就将n这个数的对应的二进制最右边的1置为了0。举例：n=11000,n-1=10001,此时n & n-1 = 10000,(另一个用法:n&n-1 这个运算就能判断n是不是2的i次幂),所以对于一个整数n，n&n-1不为0 的情况下，能持续与运算的次数，就是n的二进制对应的1的个数

    public int NumberOf1_3(int n) {
        int res = 0;
        while (n != 0) {
            res++;
            n = n & (n - 1);
        }
        return res;
    }

参考文献

负数的二进制表示方法