461. 汉明距离-蒲公英云

461. 汉明距离

男娘i 2022-10-16 07:18 256阅读 0赞

2021-05-27 LeetCode每日一题

链接：https://leetcode-cn.com/problems/hamming-distance/

标签：位运算

题目

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 2^31.

输入: x = 1, y = 4
输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

分析

连续四五天的困难题，今天终于可以重拳出击了。按照题意，只需要把x和y转换为二进制一一比较即可。最容易的就是不管数多大，全部按照32位数来转。

当然x和y可能很小，不需要32次循环就可以提前退出。

编码

普通做法：

class Solution { 
    public int hammingDistance(int x, int y) { 
        int res = 0;
        for (int i = 0; i < 32; i++) { 
            int bit1 = (x >> i) & 1;
            int bit2 = (y >> i) & 1;
            if (bit1 != bit2) { 
                res++;
            }
        }
        return res;
    }
}

时间复杂度O(1)，空间复杂度O(1)

在这里插入图片描述

更快的做法：

class Solution { 
    public int hammingDistance(int x, int y) { 
        int res = 0;
        while (x != y) { 
            if ((x & 1) != (y & 1)) { 
                res++;
            }
            x = (x >> 1);
            y = (y >> 1);
        }
        return res;
    }
}