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.
解法1:
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
out(0, 0)=0
out(0, 1)=1
out(1, 0)=1
out(1, 1)=0
out(2, 1)=2
out(4, 1)=2
out(0xffffffff, 0)=31?
1100 & 1011 = 1000
"""
z = x ^ y
res = 0
while z:
res += 1
z = z & (z-1)
return res
解法2:
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x^y).count('1')
因为:
>>> bin(12)
'0b1100'
>>> '0b1100'.count('1')
2
>>> 'abcb'.count('b')
2
解法3:
We can find the i-th bit (from the right) of a number by dividing by 2 i times, then taking the number mod 2.
Using this, lets compare each of the i-th bits, adding 1 to our answer when they are different.
Code:
ans = 0
while x or y:
ans += (x % 2) ^ (y % 2)
x /= 2
y /= 2
return ans
比较笨拙,其实 (x & 1) ^ (y & 1), x>>1,y>>1 更好!单独判断某位是否为1移位即可,当然用%2也可以。
res = 0
while x or y:
res += (x&1) ^ (y&1)
x = x>>1
y = y>>1
return res
标签:Distance,return,int,res,461,ans,type,leetcode,out From: https://blog.51cto.com/u_11908275/6381161