【LeetCode】461 Hamming Distance-CSDN博客

本文链接：https://blog.csdn.net/zhcourse/article/details/111245700

本文介绍了计算两个整数汉明距离的三种方法：直接解法、异或后计数和位操作优化。解法一通过逐位比较计算；解法二利用异或后查找1的个数；解法三使用位操作技巧，通过与运算减少循环次数，提高了效率。这些方法适用于理解位操作和优化算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

汉明距离指的是两个数字的二进制表示间对应位置的不同数字的个数。

解法一

直接解法：循环依次判断x和y的对应位是否相同，由异或判断是否相同：

int hammingDistance1(int x, int y) {
    int count = 0;

    for (int i = 0; i < 32; ++i) {
        if ((x & (1 << i)) ^ (y & (1 << i))) {
            count++;
        }
    }

    return count;
}

解法二

解法一的提升版，直接将x和y进行异或，再判断结果里1的个数：

int hammingDistance2(int x, int y) {
    int res, count = 0;

    res = x ^ y;

    for (int i = 0; i < 32; ++i) {
        if (res & (1 << i)) {
            count++;
        }
    }

    return count;
}

解法三

想要判断一个数的二进制里有多少个1，还有一个更简单的办法：

int hammingDistance3(int x, int y) {
    int res, count = 0;

    res = x ^ y;

    while (res) {
        count++;
        res &= (res - 1);
    }

    return count;
}

假设一个数里有N个1，那么时间复杂度就是O(N)，就不用循环全部的32位了，当然最坏情况还是32位都是1。

假如res=1101，res-1=1100，他俩进行与操作，结果是1100，最后一位为0，也就是找到了第一个1，将其变为0。

然后res=1100，res-1=1011，他俩进行与操作，结果是1000，从右数第3位为0，也就是找到了第二个1，将其变为0。

这样一直进行到最后，每次都将最右边的1变为0，直到res=0退出循环，就算找到了所有的1。

参考：

[LeetCode] Hamming Distance 汉明距离

最后更新于2017年6月19日。