C++计算两个整数之间的汉明距离

在信息论中,两个等长字符串之间的汉明距离(英语:Hamming distance)是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

例如,给出两个字符串abcacb之间的汉明距离就是2;

给出两个十进制数123321之间的汉明距离也是2;

而对于二进制数字来说,其汉明距离的结果就为两个数值相乘的结果中的1的个数,例如1和4所对应的二进制数值的汉明距离为2

我们可以使用XOR(或异)来实现这个计算:

class Solution {
public:
    int hammingDistance(int x, int y) {
        int z  = x ^ y;
        int r = 0;
        for (; z > 0; z >>= 1) {
            r += z & 1;
        }
        return r;
    }
};

或者使用C++ STL来解决(假定这两个整数均为32位)

class Solution {
public:
    int hammingDistance(int x, int y) {
        return bitset<32>(x^y).count();
    }
};

或者直接使用C++ 内部提供的函数:

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);
    }
};

参考