LeetCode 461. 汉明距离

2023-12-09 HGNULB 约 8 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 461. 汉明距离

题意分析

给两个整数 x、y，求它们的汉明距离，也就是把两个数写成等长的二进制串后，对应位置上数字不同的位数。

「对应位置」意味着比较是按位对齐的，不涉及任何移位或重排；「等长」则是因为整数在机器里本就是固定宽度（32 位），位数少的数高位补 0，不需要额外处理长度对齐。

约束是 0 <= x, y <= 2^31 - 1，两个数都非负，所以符号位恒为 0，不会出现负数右移时高位补 1 带来的麻烦。这个约束让写法可以放心用 >> 而不必纠结 >>>——不过后面会看到本题的主解法连移位都不需要。

题目本身没有规模压力（只有两个数、最多 31 个有效位），所以真正被考察的不是复杂度，而是能否用位运算把「逐位比较」这件事一次性完成，以及是否知道统计 1 的个数的高效技巧。这是一道典型的位运算基本功题。

边界很少：x == y 时答案是 0；其中一个为 0 时答案就是另一个数里 1 的个数。两者都应该自然落进主逻辑，不需要特判。

解法：异或计数

核心思路

最直白的做法是开一个循环跑 32 次，每次分别取出 x 和 y 的第 i 位再比较是否相等。它能算对，但每轮要做两次移位、两次按位与和一次比较，写起来啰嗦，而且「取第 i 位」的下标管理容易出错。

瓶颈在于把「比较」和「统计」两件事混在了一个循环里。如果能先一次性把「哪些位不同」标记出来，问题就退化成一个更简单的子问题。

关键观察是异或的定义：相同为 0、不同为 1。所以 v = x ^ y 之后，v 的二进制里每一个 1 恰好对应 x 与 y 不同的一位，每一个 0 对应相同的一位。汉明距离于是完全等价于「v 中 1 的个数」，两个数的问题被归约成了一个数的问题。

接下来统计 1 的个数。逐位右移检查是 $O(32)$ 的，而有一个更优的恒等式：v & (v - 1) 的效果是把 v 的最低位的那个 1 变成 0，且不影响其他位。原因是 v - 1 会把最低位的 1 翻成 0、并把它右边所有的 0 全翻成 1，高位保持不变；再与 v 做按位与，右边那些新翻出来的 1 因为在 v 里是 0 而被清掉，最低位的 1 也因为在 v - 1 里变成了 0 而被清掉，其余高位原样保留。

于是循环不变量是：每执行一次 v &= v - 1，v 中 1 的个数恰好减少 1，而 count 恰好增加 1，两者之和始终等于最初 v 里 1 的总数。初始时 count = 0，和就是初始的 1 的个数；每轮同减同增保持不变；当 v == 0 时 1 的个数为 0，count 就等于总数，循环终止并返回。

这个写法的循环次数等于 1 的个数而不是位宽，两个相近的数往往一两轮就结束，是面试官期待的标准答案。

解题步骤

先算 v = x ^ y：一步把「两个数的按位比较」压缩成「一个数的位统计」。这是本题的核心归约，也是面试时最该主动说出来的一句话。

计数器 count 初始化为 0：它的含义是「已经消掉的 1 的个数」，一个都还没消，所以是 0。这个初值同时让 x == y（v 直接为 0）的情形自然返回 0，无需特判。

循环条件写 v != 0：条件必须是「还有 1 没消完」。写成 v > 0 在本题因为两数非负、异或结果最高位为 0 而碰巧等价，但一旦输入含负数就会漏掉符号位，是不该养成的习惯。

循环体先执行 v &= v - 1：消掉当前最低位的那个 1。注意运算顺序是先减一再按位与，v & v - 1 因为 - 的优先级高于 & 恰好也对，但显式写成 v & (v - 1) 或用复合赋值更不容易误读。

紧接着 count++：每消掉一个 1 就记一笔。放在 v &= v - 1 之后或之前都不影响结果，但「先消再记」的顺序更贴合「已消个数」这个语义。

返回 count：循环退出时 v 为 0，所有不同位都已被计入。

以 x = 1、y = 4 走一遍（题目样例，答案应为 2）。

第一步：x = 0001、y = 0100，v = x ^ y = 0101（十进制 5）。可以看到第 0 位和第 2 位不同，正好对应 v 里的两个 1。

初始：v = 0101、count = 0。

第一轮：v - 1 = 0100，v & (v-1) = 0101 & 0100 = 0100。最低位的 1（第 0 位）被消掉，v 变成 4，count = 1。

第二轮：v = 0100，v - 1 = 0011，0100 & 0011 = 0000。第 2 位的 1 被消掉，v 变成 0，count = 2。

v == 0，循环退出，返回 2，与预期一致。整个过程只跑了 2 轮，而逐位检查需要跑满 32 轮。

再看两个边界。x = 3、y = 3：v = 0，循环一次都不进，返回 0，正确。x = 0、y = 7：v = 0111，三轮依次消掉三个 1，返回 3，正确。

代码实现

class Solution {
    // 用位运算统计 1 的数量即可。
    public int hammingDistance(int x, int y) {
        int v = x ^ y;
        int count = 0;

        while (v != 0) {
            v &= v - 1;
            count++;
        }

        return count;
    }
}

func hammingDistance(x int, y int) int {
    // 用位运算统计 1 的数量即可。
    v := x ^ y
    count := 0

    for v != 0 {
        v &= v - 1
        count++
    }

    return count
}

复杂度分析

时间复杂度：$O(1)$。循环次数等于 x ^ y 中 1 的个数，而整数宽度固定为 32 位，所以最多 32 轮，与输入规模无关。若按位数记则是 $O(k)$，$k$ 为 1 的个数，严格优于逐位扫描的 32 次。

空间复杂度：$O(1)$，只用了 v 和 count 两个整型变量，没有数组也没有递归。

关键点总结

异或是「找不同」的天然工具：相同为 0、不同为 1，能一步把「两个数逐位比较」归约成「一个数统计 1 的个数」。凡是涉及「有多少位不一样」「哪一位不一样」的题，先想异或。

v & (v - 1) 消去最低位的 1 是必须记牢的位运算恒等式，而且要能当场解释原理（v-1 借位翻转最低位及其右侧，按位与后只保留更高位）。面试官常追问「为什么这样能消掉」，答不出来等于只背了口诀。

循环次数由 1 的个数而非位宽决定，这类「按有效信息量收敛」的写法在稀疏位模式下优势明显；反过来若 1 很密集，它并不比逐位扫描快，说清楚这个权衡比背结论更好。

位运算符优先级低于算术与比较运算符，混用时一律加括号；这条在 dp[i>>1] + (i&1)、(v & (v-1)) 这类表达式里反复救命。

归约思路比技巧更重要：本题真正的价值是演示「把双输入问题变成单输入问题」，同样的手法在 136（异或消去成对元素）、477（按位统计）里都会再出现。

易错点总结

分别统计 x 和 y 中 1 的个数再相减：x = 3（11）、y = 5（101）时两者都有 2 个 1，会返回 0，而真实答案是 2；1 的个数相同不代表位置相同。

写成 v &= v + 1：v = 5 时 5 & 6 = 4，4 & 5 = 4，v 卡在 4 不再变化，直接死循环。

循环条件写 v > 0：本题两数非负所以碰巧等价，但一旦输入允许负数，v 为负时循环一次都不进，返回 0；养成用 != 0 的习惯才安全。

忘记先异或，直接对 x 做 x &= x - 1 计数：x = 1、y = 4 会返回 1（x 里 1 的个数），而答案是 2。

用 count 记录循环轮数却把 v &= v - 1 写在 count++ 之后并用 do-while：x == y 时 v 本就是 0，do-while 强制执行一轮，0 & -1 = 0 不报错但 count 变成 1，返回错误的 1。

改用逐位比较却把循环写成 while (x != 0 || y != 0) 并同时右移两个数：思路可行，但若漏掉 || 写成 &&，x = 0、y = 7 会在第一轮就退出，返回 0 而不是 3。

用字符串把两数转成二进制再逐字符比较：Integer.toBinaryString(1) 是 "1"、toBinaryString(4) 是 "100"，长度不同，不先左边补零对齐就会错位比较，返回 3 而不是 2。

直接调用 Integer.bitCount(x ^ y)：结果正确，但本题的全部考点就是位计数的实现，面试中会被要求手写；写库函数等于交白卷。

误以为需要处理位数对齐：整数在机器里本就是定宽的，高位自动补 0，任何手动「补齐位数」的逻辑都是多余的，还可能引入越界移位（Java 里 1 << 32 等于 1 而不是 0）。

返回 v 而不是 count：循环结束时 v 恒为 0，无论输入是什么都返回 0，只有在 x == y 时才碰巧正确。

相似题目

题目	难度	考察点
191. 位1的个数	简单	去掉异或那一步，纯粹考 `n & (n-1)` 的位计数
剑指 Offer 15. 二进制中1的个数	简单	与 191 同题，需按无符号语义处理最高位
面试题 05.06. 整数转换	简单	与本题同题，但输入可为负数，Java 需改用 `>>>` 或直接沿用消位法
477. 汉明距离总和	中等	所有数两两求距离，需按位统计 0 与 1 的个数再相乘，避免 $O(n^2)$
338. 比特位计数	简单	批量求 0 到 n 的位计数，用 `dp[i>>1] + (i&1)` 复用子结果做到线性
LCR 003. 比特位计数	简单	与 338 同题
136. 只出现一次的数字	简单	同样用异或，但利用的是 `a ^ a = 0` 的自反性来消去成对元素
260. 只出现一次的数字 III	中等	全体异或后取最低位的 1 作分组依据，是异或技巧的进阶组合
190. 颠倒二进制位	简单	必须跑满 32 轮而不能按 1 的个数收敛，因为 0 的位置同样要参与翻转
389. 找不同	简单	字符层面的「找不同」，把所有字符异或起来剩下的就是多出的那个