剑指offer----二进制中1的个数

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

解法一：

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

不断将n向右移一位，并与1相与，如果最低位为1, num就加1，直到n变为0.这里要用java中特有的无符号右移>>>，如果使用>> 负数的补码最高位永远是1，及时移到最后n的所有记数为都为0了，但符号标记位仍是1，n无论怎么移动都是- 2^31次。陷入了死循环。这个方法时间复杂度与给定的位数有关，每次移位都相当于除以2，所以是logn。

解法二：

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

这应该是目前的最优解了。
其复杂度仅仅与给定的数的1的个数有关。
1111000 - 1 = 1110111
一个二进制数减1的试过是他所有的1中最低位的1变成0，他后面的0变成1，所以将n&(n-1)，就会将最低位的1变位0，不断的循环直到把n中所有的1都替换为0即可。
11000101010，需要5此循环。其复杂度O(M)，M为给定的数的1的个数。

等等，还没完，《编程之美》一书中，给了一个比较“智障”的方法，典型的空间换时间，其时间复杂度可以做到O(1。将所有的数的1的个数都运算一遍，然后以n为下标存在一个数组里边。当然书中的用例比较小，仅仅是一个8位的二进制数。但是在一个需要频繁需要此算法的场景中，用空间换时间也是值得的。