461 汉明距离

题目信息

题目地址：https://leetcode-cn.com/problems/hamming-distance/

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 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

题解

这题看提示上面写了是正数，所以不用管负数补码。直接看数字的二进制比较即可。

很容易就能想到，肯定是哪种位运算能够get到二进制数字不同。那不就是异或和同或么，一个是不同为1相同为0，一个相反。

0101 ^ 0010 = 0111

我们使用异或运算，有几个不同，得到的结果就有几个1.

那岂不变成了上一题《位一的个数》求1的个数，直接搞过来

// 求位1的个数
public int hammingWeight(int n) {
    int num = 0;
    while(n != 0){
        n = n & (n-1);
        num++;
    }
    return num;
}

public int hammingDistance(int x, int y) {
    return hammingWeight(x ^ y)
}

这个时间复杂度也就是求为一的个数的复杂度，其实是n的长度也就是最大不过31是一个常数所以是O(1),空间复杂度也是O(1)

总结

还没思考就已经写完一大早就水了一篇文章，看了官方解题咋一看还有多解，实际上全都是“位一的个数”这题的不同解再配上异或运算。关于位一的个数解的细节可以看我这篇 191 位1的个数。