echo

任生命穿梭 时间的角落

0%

汉明距离

Posted on In Valine:

461. 汉明距离

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

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

注意：
0 ≤ x, y < 231.

示例:

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 ，相同得 0。我们对 x 和 y 做一次异或操作，得到的数的二进制位中的 1 的个数就是 x 和 y 的汉明距离。

1
2
3
4
x = 1, y = 4
1       (0 0 0 1)
4       (0 1 0 0)
1 xor 4 (0 1 0 1)  "1" 的个数为 2，即汉明距离为 2

方法一：位移

我们要求一个数字二进制位中 “1” 的个数，可以不断将数字右移，统计最后一位为 1 的个数，直到数字为 0。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int hammingDistance(int x, int y) {
        int m = x ^ y, count = 0;
        while(m != 0){
            if(m % 2 == 1){
                ++count;
            }
            m >>= 1;
        }
        return count;
    }
}

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

方法二：布赖恩·克尼根算法

「Brian Kernighan 算法」，用于清除二进制串中最右边的 1。

我们每次对 n 和 n - 1进行按位与操作后，n 中最右边的 1 会被抹去变为 0 。

image-20200823091337544

我们不断地将数字的最右边的 “1” 变为 0 ，同时统计 1 的个数，直到数字为 0 。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int hammingDistance(int x, int y) {
        int m = x ^ y, count = 0;
        while(m != 0){
            m = m & (m - 1);
            ++count;
        }
        return count;
    }
}

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