题目
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y,计算它们之间的汉明距离。
注意:
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
思路
1、暴力解法。先将x和y分别转换为二进制,在对他们进行判断有多少位不同,这里有一个关于x、y长度的判断。
2、异或。
实现方法
一、暴力解法
class Solution {
public:
int hammingDistance(int x, int y) {
vector<int> rx,ry;
int count=0;
while(x){ //将x变换为二进制
rx.push_back(x%2);
x=x/2;
}
while(y){ //将y变换为二进制
ry.push_back(y%2);
y=y/2;
}
if(rx.size()<ry.size()){
for(int i=0;i<rx.size();i++){
if(rx[i]!=ry[i])
count++;
}
for(int i=rx.size();i<ry.size();i++){
if(ry[i]==1)
count++;
}
}else if(rx.size()>ry.size()){
for(int i=0;i<ry.size();i++){
if(rx[i]!=ry[i])
count++;
}
for(int i=ry.size();i<rx.size();i++){
if(rx[i]==1)
count++;
}
}else{
for(int i=0;i<ry.size();i++){
if(rx[i]!=ry[i])
count++;
}
}
return count;
}
};
二、异或
class Solution {
public:
int hammingDistance(int x, int y) {
int k=x^y;
int count=0;
while(k){
if(k%2==1)
count++;
k=k/2;
}
return count;
}
};
版权声明:本文为weixin_43434305原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。