当前位置 : 首页 » 文章分类 :  开发  »  LeetCode.191.Number of 1 Bits

LeetCode.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.


解题过程

本来是很简单的题,依次模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代码


上一篇 LeetCode.500.Keyboard Row

下一篇 LeetCode.419.Battleships in a Board

阅读
519
阅读预计2分钟
创建日期 2018-01-13
修改日期 2018-01-14
类别
百度推荐