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