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 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/liucan9035/article/details/56679329