牛客 JZ11 二进制中1的个数

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

思路：利用二进制做与运算(&)时，只有相同位才能保持，其他均变0的特性；加上二进制每位最高为1.

所以有：对该整数a和其减1后的数b做与运算，每做一次与运算表明有1个1，所以该整数32位二进制表示中1的个数就等于做与运算的次数。

举例：以下假设4位

正整数5： 0101 & 0100 = 0100, 0100 & 0011 = 0000 -> 所以有2个1

负整数-5： 1011 & 1010 = 1010, 1010 & 1001 = 1000, 1000 & 0111 = 0000 -> 所以有3个1

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