两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y,计算它们之间的汉明距离。
注意: 0 ≤ x, y < 2^31.
示例 1: 来源:力扣(LeetCode) 链接:
题解1:
字符串计数法
执行用时:40 ms, 在所有 Python3 提交中击败了69.61%的用户
内存消耗:13.4 MB, 在所有 Python3 提交中击败了28.26%的用户
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
result = 0
bx = bin(x)
by = bin(y)
max_len = max(len(bx), len(by))
sbx = bx[2:].zfill(max_len)
sby = by[2:].zfill(max_len)
for _ in range(max_len):
if sbx[_] != sby[_]:
result = result + 1
return result
题解2:
位运算
执行用时:36 ms, 在所有 Python3 提交中击败了87.61%的用户
内存消耗:13.4 MB, 在所有 Python3 提交中击败了21.26%的用户
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x^y).count('1')
题解3:
偶数位为0,奇数位为1 0x55555555 = 0b1010101010101010101010101010101
1和0每隔两位交替出现 0x33333333 = 0b110011001100110011001100110011
0x0f0f0f0f = 0b1111000011110000111100001111
0x00ff00ff = 0b111111110000000011111111
1和0每隔两位交替出现 0x0000ffff = 0b1111111111111111
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
z = x^y
z = (z & 0x55555555) + ((z >> 1) & 0x55555555)
z = (z & 0x33333333) + ((z >> 2) & 0x33333333)
z = (z & 0x0f0f0f0f) + ((z >> 4) & 0x0f0f0f0f)
z = (z & 0x00ff00ff) + ((z >> 8) & 0x00ff00ff)
z = (z & 0x0000ffff) + ((z >> 16) & 0x0000ffff)
return z