汉明距离（PTA）

两个整数间的汉明距离指的是这两个数对应二进制位不同的位置的数目。输入两个整数x,y, 0<=x,y<=231。输出x,y的汉明距离。

输入格式:

在一行输入x,y。

输出格式:

在一行输出x,y汉明距离。

输入样例:

在这里给出一组输入。例如：

1 4

输出样例:

在这里给出相应的输出。例如：

2

传统方法解决：（原创）

#include <iostream>

#include <stack>

#include <cmath>

#include <algorithm>

using namespace std;



string zhuanhua(int n) //利用栈将十进制转化位二进制数字（注意没有补前置零，如1->1，4——》1000）
{

if (n == 0) 
{

return "0";

}



stack<char> gg;

string ff;



while (n > 0) 
{

if (n % 2 == 1) 
{

gg.push('1');

} 
else 
{

gg.push('0');

}

n /= 2;

}



while (!gg.empty()) 
{

ff.push_back(gg.top());

gg.pop();

}

return ff;

}



string buqi(string n, int l)//弥补没有前置零的情况，1-》0001
 {

if (n.length() == l) 
{

return n;//踢出无需补零的数字

}

int cha;

cha = l - n.length();

string bb;

for (int i = 0; i < cha; i++)
{

bb += '0';

}

return bb + n;//将补齐的零直接前置

}



int bijiao(string aaa, string bbb) //一位一位的比较两个等长字符串（较短的前置补零）
{

int sum = 0;

int len = bbb.length();

for (int i = 0; i < len; i++) 
{

if (aaa[i] != bbb[i]) 
{

sum++;

}

}

return sum;

}



int main() 
{

int a, b;

int n1, n2;

int len;

cin >> a >> b;

string aa, bb, aaa, bbb;

aa = zhuanhua(a);

bb = zhuanhua(b);

n1 = aa.length();

n2 = bb.length();

len = max(n1, n2);

//cout << aa << endl;//检验转化的二进制字符串

//cout << bb << endl;

aaa = buqi(aa, len);

bbb = buqi(bb, len);

//cout << aaa << endl;//检验补零后的二进制字符串

//cout << bbb << endl;

cout << bijiao(aaa, bbb) << endl;

return 0;

}

位运算方法解决：（转载[LeetCode] Hamming Distance 汉明距离 – Grandyang – 博客园 (cnblogs.com)）

#include <iostream>

#include <algorithm>

using namespace std;



int main() {

int i, sum = 0;

int x, y;

cin >> x >> y;

for (i = 1; i <= 32; i++)//比较是默认十进制已转化为二进制
{

if ((x & (1 << i)) ^ (y & (1 << i)))
//每次比较对应二进制位置上的数字是否相同，不同为1，相同为0
//(1 << i)表示，将1左移i位，(i=2)即0001->0100
//(x & (1 << i)表示x的第i位保留，其余归零，方便比较，仅对比互相对应位上的数字
{
sum++;//统计不同的次数
}

}



cout << sum << endl;

return 0;

}

声明：

1.本人学习专用，不定期更改。

2.并非个人完全原创，参考了大量其他博客。