frendguo's blog

【LeetCode】461. Hamming Distance

原文地址:https://leetcode.com/problems/hamming-distance/#/description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ xy < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ?   ?

The above arrows point to positions where the corresponding bits are different.
先分析题目,是要求两个整数的汉明距离,即求两个整数二进制对应位不相同的个数。
既然是二进制的运算,首先想到了位运算。将两个整数先进行异或运算,然后计算异或结果中‘1’的个数就是所求。
这里有标明 x,y的范围,所以就不用太注意边界错误。于是便写出了以下代码:
public class Solution {
    public int HammingDistance(int x, int y) {
        int tmp = x ^ y;
        int num = 0;
        for (int i = 0; i < 32; ++i)    
        {
            // if ((tmp & 1) == 1) ++num;
            num += tmp & 1;
            tmp >>= 1;
        }
        return num;
    }
}
然后提交,居然只击败24%~ 
细细一想,计算‘1’个数的地方还可以继续优化。于是发现了国外一个大神写的博客,点这里进去观摩》》
于是就有了下面这个代码:
public class Solution {
    public int HammingDistance(int x, int y) {
        int tmp = x ^ y;
        int num = 0;
        while (tmp != 0)    
        {
            tmp &= (tmp - 1);
	    ++num;
        }
        return num;
    }
}
再改进下,就变成下面这个样子了:
public class Solution {
    public int HammingDistance(int x, int y) {
        int tmp = x ^ y;
        int num = 0;
        tmp = tmp - ((tmp >> 1) & 0x55555555);
		tmp = (tmp & 0x33333333) + ((tmp >> 2) & 0x33333333);
		return ((tmp + (tmp >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
    }
}
然而,尴尬的来了,最后这个方法耗时居然是最高的~
猜测应该是位数太少了(32位),位数变大的话,效果应该会好点。。。
Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading