1、题目名称

Number of 1 Bits（整数的汉明重量）

2、题目地址

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