461. 汉明距离（Hamming Distance）

频次 ★★★ · 难度 🟢 · 高频：字节

题目

两个整数二进制表示不同位的个数。

思路

先异或得到不同位为 1，然后数 1 的个数。

代码

public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int count = 0;
    while (xor != 0) {
        count += xor & 1;
        xor >>= 1;
    }
    return count;
}

也可以用 Integer.bitCount(x ^ y) 一行。但面试需要手写。

复杂度

• 时间：O(位数)。逐位移位是 O(32)；换成 xor &= xor - 1 的写法是 O(1 的个数)，最好情况 O(1)
• 空间：O(1)

边界条件

• x == y：异或为 0，循环不进入，返回 0
• 本题约束 0 ≤ x, y ≤ 2^31 - 1，异或结果非负，所以 >>= 安全。若允许负数，>> 会用符号位填充高位，xor 永远不为 0，死循环——见易错点
• 有一个是 0：退化成「数另一个数里 1 的个数」

变式

• 338. 比特位计数：批量求 0~n 每个数的 1 的个数，用 DP 复用子结果
• 371. 两整数之和：同样以异或为「无进位加法」，但要把进位也算回去
• 数组里所有数两两汉明距离之和：不要 O(n²) 枚举，按位统计——第 k 位上有 c 个 1、n-c 个 0，该位贡献 c × (n-c)
• 汉明距离用于相似度：SimHash 判文本重复、感知哈希判图片相似，都是比较指纹的汉明距离

易错点

• xor >>= 1 是算术右移。本题因为约束非负而侥幸正确，但只要 xor 可能为负（比如题目允许负整数），高位就会一直补 1，循环永不终止。正确的写法是 >>>=（无符号右移）。 这是 Java 位运算最经典的坑
• count += xor & 1 不要写成 count += xor & 1 == 1——Java 里 == 优先级高于 &，会编译错误或语义反转
• Integer.bitCount() 在面试里通常不让用，但要知道它内部是 SWAR 算法（并行位计数），不是循环
• 别先把两个数转成二进制字符串再逐字符比——O(32) 的字符串操作比位运算慢一个数量级，也失去了考点

面试追问

• xor &= xor - 1 为什么能消掉最低位的 1：xor - 1 会把最低位的 1 变成 0、其右边的 0 全变 1；与一下，最低位的 1 就没了，右边保持 0。循环次数 = 1 的个数，对稀疏的数远快于逐位移位。这个技巧叫 Brian Kernighan 算法。
• Integer.bitCount 是怎么做到 O(1) 的：SWAR（SIMD Within A Register）——先两两相加、再四四相加、再八八相加，用固定的几条掩码与移位指令把 32 位并行折叠成一个计数。现代 CPU 更直接：一条 POPCNT 指令。
• 汉明距离在工程里干什么用：SimHash 把文档映射成 64 位指纹，两篇文章相似 ⇔ 指纹的汉明距离 ≤ 3。海量去重时再配合「按位分段建索引」加速查找。它的价值在于把「相似」这个模糊概念变成了一个可索引的整数。
• 和编辑距离有什么区别：汉明距离要求两串等长，只数「对应位置不同」的个数；编辑距离允许增删改，长度可不等，代价是 O(mn) 的 DP，见 72. 编辑距离。

关联题

• 同套路：136. 只出现一次的数字、338. 比特位计数 —— 同为逐位统计/异或技巧