Leetcode 461.汉明距离

题目描述：

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

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

示例 1：

1
2
3
4
5
6
7

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

示例 2：

1
2

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

提示：

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

链接：

https://leetcode-cn.com/problems/hamming-distance

题目分析

  两个数的汉明距离其实就是他们异或后 1 的个数。计算一个数 1 的个数可以用位运算解决。一种方法是右移一位一位计算。另一种就是 z 与 z-1 进行按位与，可以消掉 z 的最右一个 1，这个算法叫 Brian Kernighan 算法（我们当时判断一个数是不是 2 的幂次也是用的这个位运算，消除最右一个 1 后会直接变成 0），这样有多少个 1 只需进行多少次位运算，比右移一位一位算更快一点。

1
2
3
4
5
6
7
8
9
10
11
12

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

  时间复杂度：$O(\log z)$，其中 $z$ 表示两个数异或后的大小。我们是将其二进制化进行位运算，最差情况下每一位都要计算。
  空间复杂度：$O(1)$。我们只需要常数个变量进行位运算和记录。

  PS：官方题解中提到在工程中我们应该使用编程语言的内置函数，这样才是最快的方法。例如 C++ 的是 return __builtin_popcount(x ^ y);。而我们学习算法的时候就要学习造轮子。