题目描述
思路解析
一句话答案：LeetCode 461 汉明距离的标准解是异或加 Brian Kernighan 数 1：先算 n = x ^ y，两数所有不同的位在 n 里恰好变成 1；再循环执行 n &= (n - 1)，每次精确抹掉最低位的一个 1，循环的次数就是汉明距离。时间 O(k)（k 是不同位的个数，最多 32），空间 O(1)。
汉明距离在问什么
给两个整数 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 都非负，踩不到这个坑，但换个含负数的位运算题它就会咬人。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
思路一句话：不同位 → 异或点亮成 1 → 数 1 的个数。数 1 用 n &= (n-1) 逐个抹最低位 1。下面用 x=438、y=220 一步步演给你看。
先把 x、y、x^y 三行二进制摆出来（共 9 位，高位在左）。x^y 还没算，下面从最高位开始，逐位对比 x、y 是否相同。
第 8 位：x 是 1、y 是 0，两位不同 → 异或得 1（绿色点亮）。这就是一处「不同的位」。
第 7 位：x 是 1、y 是 1，两位相同 → 异或得 0，这一位不算「不同」。
第 6 位：x 是 0、y 是 1，两位不同 → 异或得 1（绿色点亮）。这就是一处「不同的位」。
第 5 位：x 是 1、y 是 0，两位不同 → 异或得 1（绿色点亮）。这就是一处「不同的位」。
第 4 位：x 是 1、y 是 1，两位相同 → 异或得 0，这一位不算「不同」。
第 3 位：x 是 0、y 是 1，两位不同 → 异或得 1（绿色点亮）。这就是一处「不同的位」。
第 2 位：x 是 1、y 是 1，两位相同 → 异或得 0，这一位不算「不同」。
第 1 位：x 是 1、y 是 0，两位不同 → 异或得 1（绿色点亮）。这就是一处「不同的位」。
第 0 位：x 是 0、y 是 0，两位相同 → 异或得 0，这一位不算「不同」。
x^y 全部算完了：x^y = 362。绿色的就是「不同的位」，一共 5 个 1。下面用 n &= (n-1) 一次抹掉一个 1，数清楚到底几个。
n 还不是 0，说明里面还有 1。最低位的那个 1 在第 1 位（紫框标出）。n-1 会把它及它右边变样，n &= (n-1) 正好把这个 1 抹掉。
这个 1 被抹掉，计数变成 1（灰色是已数过的位）。n 还不是 0，回到上一步继续消下一个最低位的 1。
n 还不是 0，说明里面还有 1。最低位的那个 1 在第 3 位（紫框标出）。n-1 会把它及它右边变样，n &= (n-1) 正好把这个 1 抹掉。
这个 1 被抹掉，计数变成 2（灰色是已数过的位）。n 还不是 0，回到上一步继续消下一个最低位的 1。
n 还不是 0，说明里面还有 1。最低位的那个 1 在第 5 位（紫框标出）。n-1 会把它及它右边变样，n &= (n-1) 正好把这个 1 抹掉。
这个 1 被抹掉，计数变成 3（灰色是已数过的位）。n 还不是 0，回到上一步继续消下一个最低位的 1。
n 还不是 0，说明里面还有 1。最低位的那个 1 在第 6 位（紫框标出）。n-1 会把它及它右边变样，n &= (n-1) 正好把这个 1 抹掉。
这个 1 被抹掉，计数变成 4（灰色是已数过的位）。n 还不是 0，回到上一步继续消下一个最低位的 1。
n 还不是 0，说明里面还有 1。最低位的那个 1 在第 8 位（紫框标出）。n-1 会把它及它右边变样，n &= (n-1) 正好把这个 1 抹掉。
这个 1 被抹掉，计数变成 5。n 现在是 0，再也没有 1 了 —— 一共数了 5 个 1，这就是汉明距离！
n 被消成全 0，一共消了 5 次，说明 x^y 里有 5 个 1。汉明距离（x 与 y 不同的位数）= 5。
边界先想清：相同两数距离 0，全不同的低 3 位距离 3。
两个高频追问，讲清 Kernighan 原理与其他数 1 的办法。
参考代码
def hammingDistance(x, y): n = x ^ y # 异或：不同的位变 1 count = 0 while n: n &= n - 1 # 抹掉最低位的一个 1 count += 1 return count复杂度
- 时间：O(k)，k = x^y 里 1 的个数；Kernighan 只循环「1 的个数」次（最多 32 次）
- 空间：O(1)，只用了 n、count 两个变量
易错点
面试追问把动画讲成自己的话
追问n &= (n-1) 为什么能精确抹掉最低位的一个 1？
追问除了 Kernighan，还能怎么数 1？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题