汉明距离

问题拆解

汉明距离是两个整数二进制表示中“对应位不同”的位数。比如 1 是 0001、4 是 0100，有两位不同，距离就是 2。

朴素做法是把两个数逐位取出来比较：对每一位做 (x >> i) & 1 和 (y >> i) & 1，看是否相等。能做，但要手动管理移位和位数，稍显啰嗦。

关键的观察是：异或 ^ 的定义就是“两位相同得 0、不同得 1”。所以 x ^ y 的每一个 1，恰好标记了一个不同的位。这样两个数的比较被一步合并成一个数。

异或把“逐位比较”压缩成“数 1 的个数”，问题瞬间少了一半。

异或之后数 1

def hammingDistance(x: int, y: int) -> int:
    diff = x ^ y
    count = 0

    while diff:
        diff &= diff - 1  # 每次消掉最低位的那个 1
        count += 1

    return count

这里用了 n & (n - 1) 的技巧：减 1 会把最低位的 1 变成 0、并把它右边的 0 全变成 1，再和原数相与，就正好抹掉了最低位的那个 1。有几个 1 就循环几次，比逐位移位扫描 32 遍更省，循环次数只和 1 的个数有关。

当然，直接用 bin(x ^ y).count("1") 也能通过，思路完全一样——先异或，再数 1。

复杂度

指标	复杂度	原因
时间	O(k)	k 为异或结果中 1 的个数，至多 32
空间	O(1)	只用了常数个变量

可以迁移的模式

• “两个集合/串有多少处不同”，异或常能一步定位差异；
• 需要统计二进制中 1 的个数时，n & (n - 1) 按 1 的个数循环，比逐位扫描更快；
• 位运算的诀窍是先想清楚每个运算符“对单个 bit 做了什么”，再放到整个数上。

看到“对应位不同”“翻转了哪些位”，先试试异或，它往往能把两个数的问题变成一个数的问题。