题解 | #二进制中1的个数#

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

初步想法
首先我们第一个想法就是十进制是怎么转化为二进制的呢？我们知道，用十进制数一直除以2直到商为0，得到的余数逆序排列即为二进制数，那么我们很容易想到一个while循环就可以解决问题。 但是，对于负数而言，我们需要表示出它的补码形式，而它们的补码是原码取反加1，情况很复杂不好写算法。下面代码只对非负数有效

public class Solution {
    public int NumberOf1(int n) {
        int count = 1;
        if(n == 0){
            return 0;
        }
        while(n != 1){
            if(n%2 == 1){
                count++;
            }
            n = n >> 1;
        }
        return count;
    }
}

方法1 移位法
我们在按位与时，十进制数会被当成二进制数处理，这时就不需要在分情况了。首先我们考虑用1和该数按位与,不断向右移动该数，代码如下：

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

但由于负数有符号位1，移动过程中会导致运算超时。所以我们考虑向左移动0x01,而该二进制数不动，该方法成功！代码如下：

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

方法2 技巧法
这个方法比较巧妙，就是用二进制数 & (二进制数-1)，每执行一次这样的操作，不仅可以精准定位到最右边的1，而且能将其减去，只要一直执行下去直到为零即可。

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

是不是很巧妙呢！