0461. Hamming Distance

题目信息

题号:

0461

难度:

Easy

主题:

非负整数、二进制位、对应位置、不同位计数

原题:

LeetCode 0461

重点:

比较两个整数二进制表示的对应位、前导零不影响结果、返回不同位的数量

题目重述

给定两个非负整数 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)。