LeetCode笔记：461. Hamming Distance

问题（Easy）：

TheHamming distancebetween two integers is the number of positions at which the corresponding bits are different.
Given two integersxandy, calculate the Hamming distance.
Note:
0 ≤x,y< 2³¹.
Example:

Input: x = 1, y = 4
Output: 2
Explanation:

The above arrows point to positions where the corresponding bits are different.

大意：

两个数之间的汉明距离是指其比特位的不同的个数。
给出两个整数x和y，计算汉明距离。
注意:
0 ≤x,y< 2³¹.
例子:

输入: x = 1, y = 4
输出: 2
解释:

上面的箭头指向的位置就是比特位不同的地方。

思路

题目很简单，就是比较两个数字的比特位不同之处，那就从右到左一个个比较就好了，也就是要从右往左一个个比较每比特位数字是否相同。因为实际上整数在计算机中就是以二进制存储的，所以可以用右移操作符来操作，更直白的也可以不断地除以2来右移，同时对2取模来得到每次最右边的那个数字，看看两个数取模得到的数是否一样，不一样则距离加一。需要注意的就是每次除以2时要判断数字是否已经变成0了，同样的方式判断循环是否终止。

代码（C++）：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int x1,y1,res = 0;
        while (x > 0 || y > 0) {
            x1 = x % 2;
            y1 = y % 2;
            if (x1 != y1) res++;
            
            if (x > 0) x = x / 2;
            if (y > 0) y = y / 2;
        }
        return res;
    }
};

他山之石：

用异或这个位操作符就可以记录下两个数字所有比特位不同的地方，然后同样的一个个去记录不同的个数，这里他用了一种很巧妙的方式，自己距离推演一下就知道怎么有效的了。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int dist = 0, n = x ^ y;
        while (n) {
            ++dist;
            n &= n - 1;
        }
        return dist;
    }
};

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首页