Code & Fun

第56天。

刷道水题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.

所谓的humming distance就是两个数在bit位上不同的个数,就int来说,最多就是全部不相同,也就是每个bit位都不一样,即humming distance.

我们可以利用异或来很快的求出来,异或可以让bit位不相同时置1,相同时置0.则两数异或后所得到的数中有bit位中1的个数就是humming distance:

1
2
3
4
5
6
7
8
9
int hammingDistance(int x, int y) {
int t = x^y;
int ret = 0;
while(t!=0) {
ret += (t&1);
t >>= 1;
}
return ret;
}

本文首发于Code & Fun