461. Hamming Distance
2018-11-30 本文已影响0人
Chrisbupt
Leetcode Day 2
题目:
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.
tips :
这道题的目的就是要求两个数字之间的汉明距离。两个数字之间的汉明距离是两个数字二进制下对应位不同的个数。
思路:
将两个数字的二进制进行异或运算,不同的位数得到1,将1累加起来就是两个数字的汉明距离。
⊕是XOR运算:异或运算就是如果两个数字(0或者1)相同,则输出为0; 如果两个数字(0或者1)不相同,就输出为a
- a⊕0=a
- a⊕a=0
- a⊕b⊕a= (a⊕a)⊕b=b
- python
# 先将x,y表示为二进制数, 用函数bin
# 也可以通过对该数字除以2 i次,得到的余数即为第i 位(从右开始)
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x^y).count('1')
//
ans = 0
while x or y:
ans += (x % 2) ^ (y % 2)
x /= 2
y /= 2
return ans
//
- C++
将x和y异或操作之后计算n其中二进制中1的个数,其计算的方法是通过自身n和自身减一的二进制数逐位相与,然后减一之后继续循环直至为0,这样也就将其二进制中1的个数计算出来
class Solution{
public:
int hammingDistance(int x, int y){
int dist = 0, n =x^y;
while(n){ //
++dist;
n &= n-1;
}
}
}