LeetCode 461简单位运算
汉明距离 图解题解
这道题到底在问什么
两个整数之间的「汉明距离」指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，返回它们之间的汉明距离。
- 输入
- x = 1, y = 4
- 输出
- 2
- 解释
- 1 是二进制 001，4 是二进制 100，有两列不同。
最优解：一步一步想明白
- 3最直接的做法：把 x、y 都转成二进制字符串，补齐到一样长，再逐位比较，不同就加一。能做，但你的精力全花在“怎么补零、怎么对齐下标”上了。
- 4关键一步：异或运算里，相同的位得 0、不同的位得 1。所以汉明距离，就等于 x 异或 y 之后结果里 1 的个数。补零这些杂事，异或一次全包了。
- 5x = 001，y = 100先把两个数放进同样的位宽里。x=1 看成 001，y=4 看成 100。下面要做的，就是给每一列算一次异或。
- 6z = 1??看最高列：x 这位是 0，y 这位是 1，两位不同，异或得 1。这个 1 就代表一个差异位。
- 7z = 10?中间列两个数都是 0，相同位异或得 0。这一列不算差异，不给答案贡献。
- 8z = 101最低列又不同，异或得 1。三列算完，z = 101。题目到这里已经被改写成：数 101 里有几个 1。
- 9接下来用最经典的位扫描：每一轮只看 z 的最低位，是 1 就计数，然后把 z 右移一位丢掉这位。下面把这三轮慢镜头放给你看。
- 10z = 101，ans = 0z 与 1 做与运算，只保留最低位。101 的最低位是 1，说明这里有个差异位，准备给 ans 加一。
- 11z = 101，ans = 1执行 ans 加上最低位，ans 从 0 变成 1。这一位已经数过，标记成处理完。
- 12z = 10，ans = 1z 右移一位，刚数过的最低位被挤出去，整串往右滑，z 变成 10。最低位换成了新的一位，绝不会重复数。
- 13z = 10，ans = 1现在最低位是 0，不是差异位。ans 加 0，仍然是 1。再右移：10 变成 1。
- 14z = 1，ans = 2右移后只剩最后一个 1。最低位是 1，ans 再加一，变成 2。再右移，z 就被掏空了。
- 15z = 0，ans = 2z 变成 0，while 条件不满足，循环停下。ans 记下的就是异或结果里 1 的总数，返回 2。和我们手数的答案一致。
- 18这一题要记住的不是某个 API，而是这条翻译：看到“位不同”想异或，看到“数不同位”就数 1 的个数。
- 20本题 x、y 非负不会踩，但同类题里 z 可能是负数。Java 的 z 右移如果用算术右移，最高位会一直补 1，z 永远不等于 0，死循环。所以习惯写无符号右移，三个尖括号，补 0 才安全。
- 24461 的后半段“数 z 里 1 的个数”，正是 191 位1的个数的全部。把它换成 Brian Kernighan 还能提速。想系统刷位运算，去 位运算专题，或直接做 191 位1的个数。不懂的随时问小欧。
⚠️ 容易写错的地方
✗ 错：拿十进制字符 "1" 和 "4" 逐字符比
✓ 对：比二进制位，或直接用 x ^ y
汉明距离看的是二进制对应位，跟十进制写法没关系。
✗ 错：直接 return x ^ y
✓ 对：返回 x ^ y 里 1 的个数
异或只是标出哪些位不同，还要再数出 1 的数量才是答案。
✗ 错：循环里只加 ans，忘了右移 z
✓ 对：每轮数完最低位必须把 z 右移一位
不右移就永远盯着同一位，while 永远不结束，直接死循环。
完整代码（Python / C++ / Java）
Python
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
z = x ^ y # 不同位变 1
ans = 0
while z: # 还有位没数完
ans += z & 1 # 最低位是 1 就计数
z >>= 1 # 右移，丢掉这位
return ansC++
class Solution {
public:
int hammingDistance(int x, int y) {
int z = x ^ y; // 不同位变 1
int ans = 0;
while (z) { // 还有位没数完
ans += z & 1; // 最低位计数
z >>= 1; // 右移
}
return ans;
}
};Java
class Solution {
public int hammingDistance(int x, int y) {
int z = x ^ y; // 不同位变 1
int ans = 0;
while (z != 0) { // 还有位没数完
ans += z & 1; // 最低位计数
z >>>= 1; // 无符号右移
}
return ans;
}
}套路模板 · Brian Kernighan 数 1
# 套路：要数整数 z 里 1 的个数？
# 判据：z &= z - 1 每次抹掉最低位的一个 1
def count_ones(z: int) -> int:
ans = 0
while z: # 还有 1 没抹完
z &= z - 1 # 抹掉最低位的那个 1
ans += 1 # 抹一次 = 多一个 1
return ans
# 汉明距离 = count_ones(x ^ y)// 套路：z &= z - 1 抹掉最低位的 1
int countOnes(int z) {
int ans = 0;
while (z) { // 还有 1 没抹完
z &= z - 1; // 抹掉最低位的 1
ans++;
}
return ans;
}
// 汉明距离 = countOnes(x ^ y)// 套路：z &= z - 1 抹掉最低位的 1
int countOnes(int z) {
int ans = 0;
while (z != 0) { // 还有 1 没抹完
z &= z - 1; // 抹掉最低位的 1
ans++;
}
return ans;
}
// 汉明距离 = countOnes(x ^ y)复杂度
时间复杂度
O(log C)
C = max(x, y)。每右移一次处理一个二进制位，位数约 log C；固定 32 位整数时可视作 O(1)。
空间复杂度
O(1)
全程只用 z、ans 两个整数变量，没有额外数组。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 汉明距离 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
异或后的那些 1，含义是什么？+
每个 1 表示 x 和 y 在这一位不同。所以数 1 的个数 = 不同位的个数 = 汉明距离。
除了逐位右移，还有更快的写法吗？+
Brian Kernighan：每次 z &= z - 1 直接抹掉最低位的那个 1，循环次数只等于 1 的个数，而不是整个 32 位。
复杂度怎么说？+
逐位扫描是 O(位数)，约 O(log C)；固定 32 位整数时常被当作 O(1)。Brian Kernighan 把常数项压到“1 的个数”。
如果不让用内置的 popcount / bin(z).count，能写吗？+
能，就是动画里这套：while z，ans 加 z 与 1，再右移。完全手写，不依赖任何库函数。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。