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.
该题即求两个整数的汉明距离,比如输入x=1, y=4, 则x的二进制表示为001,而y的二进制表示为100,而两个整数汉明距离的定义则是这两个整数的二进制表示中,不同的二进制位的个数,即在上面的例子中,由于001和100有2位不同,则它们之间的汉明距离为2。
解法一:简单粗暴法
将两个整数分别转成二进制,再分别比较每一位,若当前位不同,则距离加1,再比较接下来的一位。这种方法需要遍历二进制数中的所有位。
解法二:使用异或和n&(n-1)技巧
对两个二进制数进行异或,得到的结果中某位为1,则对应的原来两个数中该位是不同的。
而使用n&(n-1)可以使得n的二进制数表示中最后一位1变成0。例如n=110, n-1=101, 则n&(n-1)=100。
综上,可以对两个数进行异或之后使用n&(n-1)技巧计算不同的位数。这种方法无需遍历二进制数中的所有位, 只比较不同的位。
代码如下:
class Solution {
public:
int hammingDistance(int x, int y) {
int z = x^y;
int count = 0;
while(z){
++ count;
z &= z-1;
}
//cout << z << endl;
return count;
}
};
版权声明:本文为liucan9035原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。