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

题记：

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

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

示例 1：

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

示例 2：

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

提示：

• 0 <= x, y <= 2 ^ 31 - 1

题目来源：
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnyode/
来源：力扣（LeetCode）

解题方法：

x和y都转化为二进制的时候，在相同的位置上如果值都一样，他们的汉明距离就是0。如果在相同的位置上值不一样，有多少个不一样的位置，那么汉明距离就是多少。所以看到这道题，我们应该最容易想到的就是先异或运算，然后再计算这个异或运算的结果在二进制表示中1的个数。代码如下

public int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}

一行代码搞定，这题实际上没什么难度，我们只需要计算x和y的异或结果，然后再计算这个结果的二进制中1的个数即可。在之前我们分3个系列分别讲到了二进制中1的个数

《位1的个数系列（一）》
《位1的个数系列（二）》
《位1的个数系列（三）》

当然这题答案非常多，下面我们再来看两种写法

一：右移

public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int res = 0;
    while (xor != 0) {
        res += xor & 1;
        xor = xor >>> 1;
    }
    return res;
}

转换为PHP代码为：

function hammingDistance($x, $y) {
    $xor = $x ^ $y;
    $count = 0;
    while($xor != 0){
        $count += $xor & 1;
        $xor = $xor >> 1;
    }
    return $count;
}

二：不通过移位计算

前面两种方式要么是移动原数字，要么是移动1，这次我们不移动任何数字来计算。在位运算中有这样一个操作，就是n&(n-1)可以把n最右边的1给消掉。举个例子，当n=12的时候，我们来画个图看一下

明白了这个知识点，代码就很容易写了，我们通过循环计算，不断的把n右边的1给一个个消掉，直到n等于0为止

public int bitCount(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

我们还可以把它给为递归的写法，直接一行代码搞定

public int bitCount(int n) {
    return n == 0 ? 0 : 1 + bitCount(n & (n - 1));
}

转换为PHP代码为：

function hammingDistance($x, $y) {
    $xor = $x ^ $y;
    $count = 0;
    while($xor != 0){
        $count += 1;
        $xor &= $xor - 1;
    }
    return $count;
}

方法来源：
作者：数据结构和算法
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnyode/?discussion=TsikCY
来源：力扣（LeetCode）文章来源地址https://www.toymoban.com/news/detail-614338.html

到了这里，关于汉明距离，两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！