面试题10：二进制中1的个数

可能引起死循环的解法

先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位，此时原来处于从右边数起的第二位被移到最右边了，再判断是不是1。这样每次移动一位，直到整个整数变成 0 为止。现在的问题变成怎么判断一个整数的最右边是不是1了。这很简单，只要把整数和1做位与运算看结果是不是0就知道了。1除了最右边的一位之外所有位都是0。如果一个整数与1做与运算的结果是1，表示该整数最右边一位是1，否则是0。

public int HammingWeight(uint n)
{
    var count = 0;
    while (n!=0)
    {
        if ((n & 1) == 1)
        {
            count++;
        }
        n >>= 1;
    }
    return count;
}

上面的函数如果输入一个负数，比如0x80000000，运行的时候会发生什么情况？把负数0x80000000右移一位的时候，并不是简单地把最高位的1移到第二位变成0x40000000，而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。

常规解法（书中解法没整明白 啊啊啊啊）

为了避免死循环，我们可以不右移输入的数字i。首先把i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次低位是不是1……这样反复左移，每次都能判断i的其中一位是不是1。

能给面试官带来惊喜的解法

一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

public int HammingWeight(uint n)
{
    var count = 0;
    while (n>0)
    {
        count++;
        n = (n - 1) & n;
    }
    return count;
}