LeetCode191. 位1的个数

LeetCode191. 位1的个数

题目描述

image.png

方法1 右移32次

我们直观地统计二进制中每一位是否包含1。
做法是:
1、使用 n & 1 得到二进制末尾是否为 1;
2、把 n 右移 1 位,直至n=0;
于是我们可以写出以下的代码(我真的写出了这样的代码...):

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n!=0){
            res += n&1;
            n = n>>1;//算术右移
        }
        return res;
    }
}

结果:这里有坑,以后注意了

在Java中上面的代码看似没毛病,但实际上有问题的。
首先在Java中 负数的高位补码用1补,然后还有下面2种位移运算符:

算术右移 >> :舍弃最低位,高位用符号位填补;
逻辑右移 >>> :舍弃最低位,高位用 0 填补。

于是对于负数而言,其二进制最高位是 1,如果使用算术右移,那么高位填补的仍然是 1。也就是 n 永远不会为 0陷入死循环。
解决方案就是在上面的代码中用逻辑右移就可以了;

优解:n & (n - 1)

n & (n - 1) ,这个代码可以把 n 的二进制中,最后一个出现的 1 改写成 0。

图示:
image.png
因此 执行k次n&(n-1)使得n=0,k就是n的二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res ++;
            n &= n - 1;
        }
        return res;
    }
}