汉明距离

难度: Easy

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

给你两个整数 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³¹ - 1

Submission

运行时间: 21 ms

内存: 16.0 MB

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # 初始化
        dis = 0
        # 转化成俩列表
        ls1=bin(x)[2:].zfill(32)
        ls2=bin(y)[2:].zfill(32)
        for i in range(32):
            if ls1[i]!=ls2[i]:
                dis+=1
        return dis

            
        
            
                

        print(num1,num2)

Explain

这个题解的思路是先将两个整数x和y转化为32位的二进制字符串表示，不足32位的在左侧用0填充。然后逐位比较这两个二进制字符串，统计有多少个位置的字符不同，即为汉明距离。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # 初始化汉明距离为0
        dis = 0
        # 将整数x转化为32位二进制字符串表示
        ls1 = bin(x)[2:].zfill(32)
        # 将整数y转化为32位二进制字符串表示
        ls2 = bin(y)[2:].zfill(32)
        # 遍历32位二进制字符串
        for i in range(32):
            # 如果对应位置字符不同，汉明距离加1
            if ls1[i] != ls2[i]:
                dis += 1
        # 返回汉明距离
        return dis

Explore

选择将整数转化为32位二进制字符串来处理而不是直接进行位运算，可能是为了提高代码的可读性和易理解性。使用二进制字符串可以让逻辑更加直观，尤其是对于不熟悉位运算的初学者。然而，这种方法在性能上通常不如位运算，因为字符串操作相对来说会更慢一些。

使用`zfill(32)`确保二进制字符串长度为32位是为了处理Python中的整数，这些整数在内部表示时不受传统32位限制，可以是任意大的。尽管整数可能大于2^31，但由于Python的整数类型是不限大小的，使用`zfill(32)`可以确保即使整数是负数或超过32位，输出仍然是32位的二进制表示。这确保了处理的一致性，但对于大于32位的整数，这种处理方式可能会丢失高位的信息。

在比较两个二进制字符串的对应位置时，可以通过位运算来优化这一过程。使用位运算如XOR（异或），可以直接得到两个数字在每个位上的差异，然后通过计算结果中1的个数（通过位移和计数操作）来确定汉明距离，这种方法通常比处理字符串要快很多。此外，某些语言提供内置的函数来计算位中1的个数，如Python的`bin(x).count('1')`，可以进一步简化实现。

在实际应用中，基于位运算的处理方式通常比基于字符串的处理方式有更好的性能。位运算直接在数字的二进制表示上操作，避免了字符串处理的开销，如内存分配和字符比较等。位运算更加高效，尤其是在处理大量数据或要求较高性能的系统中，性能差异会更加明显。因此，在性能敏感的应用中推荐使用位运算方法。