The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x
and y
, calculate the Hamming distance.
Note:0 ≤ x
, y
< 231.
Example:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
解题思路：
Python中由个bin函数可以返回数字的二进制表达式，另外异或操作可以得到位数不同。不过不知道为啥return bin(x^y).count("1")超时了。。。
n&(n-1)可以得到二进制中1的个数。
对x^y的值用一个变量表示，1的个数用另外一个变量表示，使用x&(x-1)依次得到1的个数，直到x&(x-1)为0。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x^y).count("1")
def hammingDistance2(self, x, y):
x = x^y
y = 0
while x:
y += 1
x = x&(x-1)
return y
def hammingDistance3(self, x, y):
diff = x^y
res = 0
while diff:
diff&=(diff-1)
res+=1
return res
if __name__ == '__main__':
sol = Solution()
x = 4
y = 1
print sol.hammingDistance(x, y)
print sol.hammingDistance2(x, y)
print sol.hammingDistance3(x, y)
