题目

难度：★☆☆☆☆
类型：数学

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

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

注意：
0 ≤ x, y < 231.

示例

输入: x = 1, y = 4

输出: 2

解释:

1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

解答

方案1：计数

这道题很简单，最简单的思路是将两个字符转为二进制数，然后一一比较各位，统计不相等的个数。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        def dec2bin(x):
            """
            将十进制数转换为二进制数，以从低到高位的列表形式
            例如输入：6，输出：[0, 1, 1]
            :param x: 输入十进制数
            :return: 逆序二进制各位列表
            """
            res = []
            while x:
                r, x = x % 2, x // 2
                res.append(r)
            return res

        def hamming(a: list, b: list):
            """
            计算两个二进制数的汉明距离
            :param a: 输入两个二进制各位逆序列表
            :param b: 
            :return: 
            """
            count = 0                                   # 初始化计数器
            for i in range(max(len(a), len(b))):
                a_bit = a[i] if i < len(a) else 0       # 提取a列表当前位
                b_bit = b[i] if i < len(b) else 0       # 提取b列表当前位
                count = count if a_bit == b_bit else count + 1  # 如果提取出的两个数字不相等，计数器+1
            return count

        return hamming(dec2bin(x), dec2bin(y))

方案2：异或

汉明距离的本质是两个数异或后字符"1"的个数，可以直接使用异或实现。

两数异或后相同的位计算结果为零，不同的位计算结果为一。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y).count('1')

如有疑问或建议，欢迎评论区留言~