题解——汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：

输入：x = 3, y = 1
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/hamming-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

想要解这一题对初学者来说最直观的方法就是将给的每个数进行转化，转化成二位数字，存储到数组中。由于转化二进时高位在前低位在后，所以在比较是需要从数组的末尾往前比较，但两个数组的长度肯定是不相同的，所以在短的那个比较完后，长数组余下的每一位是1便加1，是0则不进行操作，显然这是很麻烦的，我们也可以设置两个足够长的数组并赋初值为0，这样就能让两个数组从头到尾进行比较。当然这种方法还有更简洁的写法，如下

int hammingDistance(int x, int y){
    int i=0;
    for(;x!=0||y!=0;)
    {
        if(x%2!=y%2)
        i++;
        x/=2;
        y/=2;
    }
    return i;
}

使用一个for循环，当x，y都为0是结束，为此循环进行以此判断，这个判断的意义就是x，y二进制的相同位是否相等，不相等那就计数一次，然后对x，y除以二以便于下次循环求二进制。

另一种方法就是不直接对x，y的二进制进行比较而是通过异或对两个数据进行合成，异或的意义就是当相同位相同时为0，不相同时为1；进行异或之后只需要记录数据中1的个数就能得到汉明距离。

这也就有牵涉到了计数问题，其实大多数编程语言都内置了计算二进制表达中 11 的数量的函数。在工程中，我们可以直接使用内置函数。

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

其中__builtin_popcount(x ^ y);函数就是内置计数函数。当然可以自己写一个函数来进行计数

例如使用移位进行计数

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

当然对于我这样的小白还是对循环体情有独钟，具体代码就不在写了，这是一道难度并不大的题，但是能激发我们更多的编程思路，尽可能的简化代码。