Hamming Distance

Nov 22, 2017

第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:

int hammingDistance(int x, int y) {
    int t = x^y;
    int ret = 0;
    while(t!=0) {
        ret += (t&1);
        t >>= 1;
    }
    return ret;
}
LeetCodeLeetCode

Counting Bits

Find the Duplicate Number

comments powered by Disqus