LeetCode.191.Number of 1 Bits
题目描述
- 191 Number of 1 Bits
https://leetcode.com/problems/number-of-1-bits/description/
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.
解题过程
本来是很简单的题,依次模2取余数之和,但忽略了输入是无符号整型。
其实我都不知道java中的所有整型都是有符号的,java不支持无符号整型。
第一提交后得了个Wrong Answer,错误用例是:2147483648 (10000000000000000000000000000000)

不知道后台是怎么把这个数传给int类型的参数的,反正我本地直接用2147483648测试,连编译都通不过

后来专门查了java中怎么处理无符号整型,原来都要转为更多位数的整型类型(比如用int表示无符号short,用long表示无符号int),所以转为long型提交一次,通过了:
package _191_NumberOf1Bits;
class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
long unsignedn = n & 0xFFFFFFFFL; //用long型表示无符号int
int result=0;
while(unsignedn>0){
result += unsignedn%2;
unsignedn = unsignedn/2;
}
return result;
}
}
public class NumberOf1Bits {
public static void main(String[] args){
Solution solution = new Solution();
//Integer.MAX_VALUE: (2^31)-1, 2147483647
//Integer.MAX_VALUE+1: -2^31, -2147483648
System.out.println(solution.hammingWeight(Integer.MAX_VALUE));//2147483648
}
}
又看了看这道题的Discuss,学到了很多东西。Discuss中的高端答案如下:
public static int hammingWeight(int n) {
int ones = 0;
while(n!=0) {
ones = ones + (n & 1);
n = n>>>1;
}
return ones;
}
注意两点:
- 1、右移1位(也就是除以2)要用逻辑右移(无符号右移)操作符
>>>
,保证高位永远补0 - 2、循环结束条件必须是
n!=0
,不能用n>0
,因为无符号测试用例2147483648在java中表示-2147483648,如果用n>0判断直接无法进入循环。
还有人提到,Integer
类直接就提供一个计算整型的二进制表示中1的数量的方法:Integer.bitCount(int i)
,返回指定 int 值的二进制补码表示形式的 1 位的数量
GitHub代码
- 191 Number of 1 Bits
https://github.com/masikkk/leetcode-java/tree/master/problems/_191_NumberOf1Bits
下一篇 LeetCode.419.Battleships in a Board