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)``。