美文网首页
191. Number of 1 Bits

191. Number of 1 Bits

作者: AlanGuo | 来源:发表于2016-10-30 03:10 被阅读0次

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        
    }
}

Solution:

这题关键在于理解注释里面那句话的意思:虽然传入的是整型 int n,但你也要当它是 unsigned value。一开始不理解这句话的含义,挂了2^32次方的 case。实际的意思是,传入了二进制表示为1000 0000 0000 0000 0000 0000 0000 0000的 int,但要当他是 unsigned 的。因为 Java 编译器会将二进制为1000 0000 0000 0000 0000 0000 0000 0000的 int 解释为 -(2^31),但题目需要我们当做+2^31处理。

public class Solution
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n)
    {
        //long num = ((long)n & 0x0ffffffff);
        int num = n;
        int count = 0;
        while(num != 0)  // instead of (num > 0). be careful here.
        {
            if(num % 2 != 0)
            {
                count ++;
            }
            num = num >>> 1;  // instead of >> . be careful here.
        }
        return count;
    }
}

注意1: 不能用 num > 0 做 while 循环判断条件,因为最高bit 位为1的 int 被编译器当做负数,永远不会进入 while 循环。
注意2:不能使用 >> 算数右移,因为最高bit 位为1的 int 用算术右移时,最高位不动,而从最高位右侧开始补0,最高位的1永远不会向左移。要使用 >>> 逻辑you'yi

相关文章

网友评论

      本文标题:191. Number of 1 Bits

      本文链接:https://www.haomeiwen.com/subject/gkoyuttx.html