Hamming Distance

LeetCode

第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;
}