汉明距离 图解题解

汉明距离在问什么

给两个整数 x 和 y，问它们的二进制表示里有多少个「对应位置」上的位不一样，这个数目就叫汉明距离。比如 x = 1（二进制 001）、y = 4（二进制 100），第 0 位和第 2 位都不同，距离为 2。注意比的是同一位号上的两个位——把两个数各自的 1 数出来相减是不对的，位置错开的 1 互相抵不了账。

为什么第一步是把 x 和 y 异或

直觉做法是逐位对比：对每个位号 b 取出 (x >> b) & 1 和 (y >> b) & 1 比较，不同就计数。能做对，但其实二进制世界里早有一个运算天生就在做「逐位比不同」——异或：两位不同得 1，相同得 0。一句 n = x ^ y，32 个位置的对比一次做完，所有不同的位在 n 里被点亮成 1，问题瞬间化简成「数 n 里有几个 1」，也就是求 n 的 popcount（位计数）。

n 与 n-1 按位与为什么恰好抹掉一个 1

数 1 的经典技巧是 Brian Kernighan 算法：只要 n 不为 0，就执行 n &= (n - 1)，每执行一次计数加一，n 归零时计数就是 1 的个数。它成立的原理在减 1 的借位上：n - 1 会把 n 最低位的那个 1 变成 0，并把它右边的 0 全部变成 1，而更高的位纹丝不动。再和 n 按位与，最低位那个 1 及其右边全部归零，高位原样保留——一次操作，精确消掉恰好一个 1，不多不少。

所以循环体每转一圈，n 里的 1 就少一个；转了几圈，n 里原本就有几个 1。计数和消位绑在同一个动作里，这就是它优雅的地方。

Kernighan 比逐位右移扫描快在哪

逐位扫描（n & 1 配合 n >>= 1）要一直移到最高的有效位，循环次数由位宽决定，32 位整数就是最多 32 圈，跟 1 的多少无关。Kernighan 的循环次数只等于 1 的个数：x ^ y 里只有 3 个 1，就只转 3 圈。最坏情形两者同阶，但稀疏时 Kernighan 明显省。工程上还有更快的路——很多语言和 CPU 提供内建 popcount（比如 C++ 的 __builtin_popcount），一条指令出结果；面试则更看重你能讲清 n & (n - 1) 的借位原理。

复杂度与一个负数陷阱

时间 O(k)，k 是 x ^ y 中 1 的个数，上限是整数位宽（32），所以也可以说 O(1)；空间 O(1)，全程只有 n 和 count 两个变量。

一个值得记住的陷阱：如果用逐位右移的写法去数负数，在做算术右移的语言里高位会不断补 1，循环永远到不了 0，直接死循环；要改用逻辑右移或先转成无符号数。本题约束 x、y 都非负，踩不到这个坑，但换个含负数的位运算题它就会咬人。

Python

def hammingDistance(x, y):
    n = x ^ y          # 异或：不同的位变 1
    count = 0
    while n:
        n &= n - 1     # 抹掉最低位的一个 1
        count += 1
    return count

C++

int hammingDistance(int x, int y) {
    int n = x ^ y;          // 异或：不同的位变 1
    int count = 0;
    while (n) {
        n &= (n - 1);       // 抹掉最低位的一个 1
        ++count;
    }
    return count;
}

Java

public int hammingDistance(int x, int y) {
    int n = x ^ y;          // 异或：不同的位变 1
    int count = 0;
    while (n != 0) {
        n &= (n - 1);       // 抹掉最低位的一个 1
        count++;
    }
    return count;
}