LeetCode Hamming Distance

LeetCode Hamming Distance

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 ≤ x, y < 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.

求两个整数的汉明距离,即两个整数的二进制串中不一样的位数。马上联想到之前LeetCode Number of 1 Bits求二进制中1的个数,这里是一样的,相当于求两个整数的二进制位,每次比较一下,如果不同,则汉明距离加1;当发现两个数已经相等时,汉明距离不可能再增加了。

完整代码如下:

class Solution {
public:
	int hammingDistance(int x, int y) {
		int dist = 0;
		for (int i = 0; i < 32; i++) {
			if (x == y)break;
			if ((x & 1) != (y & 1))dist++;
			x >>= 1;
			y >>= 1;
		}
		return dist;
	}
};

本代码提交AC,用时0MS,击败55.12%,加了那个break效率会高很多。

Leave a Reply

Your email address will not be published. Required fields are marked *