0461. Hamming Distance¶
题目信息¶
- 题号:
0461
- 难度:
Easy
- 主题:
非负整数、二进制位、对应位置、不同位计数
- 原题:
- 重点:
比较两个整数二进制表示的对应位、前导零不影响结果、返回不同位的数量
题目重述¶
给定两个非负整数 x 和 y,返回它们的汉明距离。汉明距离是两个整数的二进制表示中,对应位置取值不同的位数。
x 和 y 位于 [0, 2^31-1]。可以把较短的二进制表示在高位补零后比较;只返回不同位数量,不需要返回具体位置。
自建示例¶
多个二进制位不同:
输入:x = 10,y = 13
输出:3
解释:10 的二进制为 1010,13 为 1101,对应的低四位中有三个位置不同。
两个数相同:
输入:x = 6,y = 6
输出:0
解释:所有对应二进制位都相同,因此汉明距离为 0。
异或保留所有不同位¶
对两个整数做按位异或:相同位得到 0,不同位得到 1,因此汉明距离就是异或结果中 1 的个数。逐位检查并右移即可,不需要显式补齐两个二进制字符串的前导零。
C++ 实现¶
class Solution {
public:
int hammingDistance(int x, int y) {
unsigned int difference =
static_cast<unsigned int>(x ^ y);
int answer = 0;
while (difference != 0) {
answer += difference & 1u;
difference >>= 1;
}
return answer;
}
};
代码分析¶
异或后的每个 1 与一个不同的二进制位置一一对应,逐位累加不会遗漏高位;输入为非负且不使用符号位,转为无符号类型后右移语义明确。最多检查 31 位,时间复杂度为 O(log(max(x,y))),额外空间复杂度为 O(1)。