LeetCode 汉明距离题解

LeetCode 汉明距离题解

题目描述

给定两个整数 x 和 y，计算汉明距离，即两个数字对应二进制位不同的位置的数目。

示例：

输入：x = 1,y = 4
输出：2

解题思路

方法：位运算

思路：

• 使用位运算来解决这个问题。
• 将 x 和 y 进行异或运算，结果中 1 的个数就是汉明距离。
• 使用 Brian Kernighan 算法计算异或结果中 1 的个数。

复杂度分析：

• 时间复杂度：O(k)，其中 k 是整数的位数。
• 空间复杂度：O(1)。

代码实现

方法：位运算

# 汉明距离（位运算）defhamming_distance(x,y):xor=x^y count=0whilexor:xor&=(xor-1)count+=1returncount# 测试deftest_hamming_distance():x=1y=4print(hamming_distance(x,y))# 输出：2x=3y=0print(hamming_distance(x,y))# 输出：2if__name__=="__main__":test_hamming_distance()

测试用例

测试用例 1：基本情况

输入：x = 1,y = 4
输出：2

测试用例 2：另一个例子

输入：x = 3,y = 0
输出：2

总结

汉明距离是一个经典的位运算问题，它可以通过位运算来高效地解决。

位运算的核心思想是：将 x 和 y 进行异或运算，结果中 1 的个数就是汉明距离。

掌握位运算的使用方法，对于解决类似的问题非常重要。