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

原创
2015/08/12 16:56
阅读数 529

1、题目名称

Number of 1 Bits(整数的汉明重量)

2、题目地址

https://leetcode.com/problems/number-of-1-bits/

3、题目内容

英文:Write a function that takes an unsigned integer and returns the number of ’1' bits it has.

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

例如,32位整型数字11的可以用二进制数字“00000000000000000000000000001011”表示,它的汉明重量就是3。

4、解题方法

本问题可以使用位运算来解决。每次循环都将数字右移一位,然后观察移位后的数字是奇数还是偶数,如果是奇数说明最后一位是1,否则说明最后一位是0。当最后输入的数字经过不断的右移变为0时,结束循环。

一开始我写的代码是这样的:

/**
 * 功能说明:LeetCode 191 - Number of 1 Bits
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月12日
 */
public class Solution {

    /**
     * 求数字的汉明重量
     * @param n 数字
     * @return 汉明重量
     */
    public int hammingWeight(int n) {
        
        int counter = 0;
        while (n != 0)
        {
            if (n % 2 != 0) {
                counter++;
            }
            n = n >> 1;
        }
        return counter;
    }
}

不过这段“看上去没有什么问题”的代码在提交后会爆出TLE(Time Limit Exceeded)的错误。

后来我找了一下原因,发现导致判定出错时输入为2147483648,但这个输入超过了Java语言中整型的上限。后来我看了一下其他语言的题目,比如C++是这样的:

class Solution {
public:
    int hammingWeight(uint32_t n) {   

    }
};

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

一段可以AC的Java代码如下:

/**
 * 功能说明:LeetCode 191 - Number of 1 Bits
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月12日
 */
public class Solution {

    /**
     * 求数字的汉明重量
     * @param n 数字
     * @return 汉明重量
     */
    public int hammingWeight(int n) {
        
        int counter = 0;
        while (n != 0)
        {
            if (n % 2 != 0) {
                counter++;
            }
            n = n >>> 1;
        }
        return counter;
    }
}

附:Java中的三个用于移位的位运算符:>>、<<、>>>

  1. >>是带符号右移,负数高位补1,正数补0

  2. <<左移不管负数还是正数,在低位永远补0

  3. >>>是不带符号右移,不论负数还是正数,高位补0

END

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部