题目介绍

力扣461题：https://leetcode-cn.com/problems/hamming-distance/

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。

分析

汉明距离（Hanming Distance）是用于统计两段信息之间差异的概念，有很多用途：在信息论中用来量化字符串的差异，在信息编码中用于错误检测。

对于两个字符串而言，汉明距离就是对应位置的不同字符的个数；对两个整数而言，汉明距离是对应位置上数字不同的位数。本题的目的，就是求出两个整数之间的汉明距离，也就是求它们二进制表示中不同的那些位的数量。

对于两个二进制数中的“某个位”，相同的不予统计，只统计那些不同的。这自然让我们联想到位运算中的“异或”：对应位相同为0，相异为1。所以我们要做的，就是对两个数x和y做异或，然后统计结果中为1的位的个数。

方法一：利用语言内置方法

大多数编程语言中，都存在各种内置计算等于 1 的位数函数。例如Java中，Integer类就提供了bitCount方法，用于统计某个整数中1的个数。

代码如下：

public class HammingDistance {
    // 方法一：直接调库
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

复杂度分析

• 时间复杂度：O(1)。主要有两个操作：异或操作，花费常数时间；另外还用调用内置的 bitCount 方法。Java中的bitCount只进行了有限次位移、位与和相加操作，所以时间复杂度为O(1)。
• 空间复杂度：O(1)，只使用常数空间保存结果。

方法二：逐个移位

解决算法问题时，直接调库可能会受到面试官的质疑。所以我们最好还是自己实现一个统计位个数的方法。

最直观的想法就是，我们可以逐个右移每一位，然后判断当前最后一位是否为1，统计个数。判断某一位为1最简单的方法，就是和1做位与操作。当然，末位为1，代表这是一个奇数，所以我们用算术方法取模来判断也是可以的。

代码如下：

// 方法二：逐位右移
public int hammingDistance(int x, int y) {
    int xor = x ^ y; 
    int count = 0; 
    // 逐位右移，判断最后一位是否为1
    while ( xor != 0 ){
        // 如果跟1做位与结果是1，那么最后一位就是1
        if ( (xor & 1) == 1) count ++;
        xor >>= 1; 
    }
    return count;
}

复杂度分析

• 时间复杂度：O(1)。主要考察while循环的次数。Java中int类型是固定的32位，所以最多需要32次位移判断。时间复杂度为O(1)。
• 空间复杂度：O(1)，只用到了常数个临时变量。

方法三：快速移位（布莱恩·柯尼根算法）

面的方法我们是逐位移动，尽管时间复杂度是O(1)，但依然显得有些繁琐。
其实我们发现，对于人类来说，用肉眼直接判断会更容易：因为我们可以直接忽略那些0，找到一个个的1，数出来就可以了。

这种“跳过0”的快速计数方法，需要我们能够直接找到最右端的一个1，然后将后面的所有0直接删掉。

我们可以用x和x-1进行位与，当x是2的幂时，结果就是0；如果不是2的幂，其实就相当于将最后一个1，以及后面的所有0消去了，前面不受影响。

样，我们只需每次消去最右端的1以及它后面的0，直到结果为0。消去操作的次数，就是1的个数。
这种解法叫做布莱恩·柯尼根位计数算法。该算法发布在 1988 年 《C 程序设计语言第二版》（）的练习中。

代码如下：

// 方法三：快速右移
public int hammingDistance(int x, int y) {
    int xor = x ^ y; 
    int count = 0; 
    // 快速右移，跳过最后一个1之后的所有0
    while ( xor != 0 ){
        xor &= xor - 1; 
        count ++;
    }
    return count;
}

复杂度分析

• 时间复杂度：O(1)。与方法二类似，主要考察while循环的次数。由于跳过了所有的0，所以循环执行的次数，就是1的个数count，最坏情况下为32。相比之下，所做的迭代操作更少了。
• 空间复杂度：O(1)，只用到了常数个临时变量。