二进制中 1 的个数

题目描述

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

解题思路

利用二进制位与操作，记录 1 的个数。

需要注意必须使用无符号位移 >>> ，否则这里负数会出现无限循环。

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

最优解：

说是有几个 1 就执行几次循环，比上面的更好，不过没看懂。

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