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中由個(gè)bin函數(shù)可以返回?cái)?shù)字的二進(jìn)制表達(dá)式闪檬，另外異或操作可以得到位數(shù)不同肝谭。不過(guò)不知道為啥return bin(x^y).count("1")超時(shí)了著蟹。命贴。。
n&(n-1)可以得到二進(jìn)制中1的個(gè)數(shù)嗓袱。
對(duì)x^y的值用一個(gè)變量表示扯旷，1的個(gè)數(shù)用另外一個(gè)變量表示，使用x&(x-1)依次得到1的個(gè)數(shù)索抓，直到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)
