力扣 461. 汉明距离

题目说明

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

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

  • 提示：

    • 0 ≤ x, y < 2^31.

示例

示例 1：

1
2
3
4
5
6
7
8
9
10
输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

笔者理解

此题是一道位运算算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题考察的是二进制数计算的性质，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public int hammingDistance(int x, int y) {
        int result = 0;
        
        // 通过异或求出两个数的不同位构成的数
        int temp = x ^ y;
        while(temp != 0) {
            // 再将数通过逐位消除1来求出二进制数中1的个数
            // n & n-1 可以消除 n 二进制数最右边的1
            temp &= (temp - 1);
            result++;
        }
        return result;
    }

时间和空间效率都还行，可见此解法还比较适合此题；

image-20210527100949059

总结

本题是今天的一题，难度是为简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。