191. Number of 1 Bits   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.


大体意思

写一个函数,输入一个无符号整数,返回其中值为 1 的比特位的个数(这个值也被称为数字汉明重量)

自己的思路

循环判断最后一位是否是 1

public int hammingWeight(int n) {
 int result = 0;
 while (n != 0) {
  if ((n & 1) == 1) {
   result++;
  }
  n = n >> 1;
 }
 return result;
}

在 Submit Solution

Submission Result: Time Limit Exceeded
Last executed input: 2147483648 (10000000000000000000000000000000)

别人的算法

2147483648 输入超过了 Java 语言中整型的上限

原来问题就出在输入可能是无符号数字上!当输入为 2147483648 时,Java 会将这个数字判断位 -1,而右移符号 » 在计算时会保持数字的符号位,即正数右移高位补 0,负数右移高位补 1。使用这种规则进行右移,会导致数字在右移过程中被不断补 1,这样循环永远无法停止!因此,如果输入为负数,也应该保持右移时高位补 0,位运算符 »> 可以帮助我们解决这个问题。

public int hammingWeight(int n) {

 int counter = 0;
 while (n != 0)
 {
     if (n % 2 != 0) {
  counter++;
     }
     n = n >>> 1;
 }
 return counter;
}
  1. >> 是带符号右移,负数高位补 1,正数补 0
  2. << 左移不管负数还是正数,在低位永远补 0
  3. >>> 是不带符号右移,不论负数还是正数,高位补 0

引用:LeetCode:Number of 1 Bits-整数的汉明重量-Tsybius2014

别人的算法 2

补码:正数为其本身,负数为取反加一

// you need to treat n as an unsigned value
public int hammingWeight(int n) {
 long l = Integer.toUnsignedLong(n);
 int count = 0;
 for (; l != 0; l = l >> 1) {
     if ((l & 1) == 1) count ++;
 }
 return count;
}

所以在 Java 中需要将 int 转换为 unsigned int 的时候,可以将 int 转换到容量更大的 long 中就行了,直接 ((long) x) & 0xffffffffL 或者使用函数 Integer.toUnsignedLong()

引用:nekocode/leetcode-solutions-191. Number of 1 Bits