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