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
网友评论