461. 汉明距离

Posted on | In
Words count in article: 559 | Reading time ≈ 2

题目

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

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

示例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)
       ↑   ↑

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

示例2：

1
2
输入：x = 3, y = 1
输出：1

提示：

  • 0 <= x, y <= 2^31 - 1

解法

解法一：

现将两个整数转换为二进制字符串，然后填充0至一样的长度，按照位计算不同的个数即可。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int hammingDistance(int x, int y) {
        String sx = fillWithZero(Integer.toBinaryString(x));
		String sy = fillWithZero(Integer.toBinaryString(y));
        return calDiff(sx, sy);
    }
	
	private String fillWithZero(String s) {
		while (s.length() < 32) {
			s = '0' + s;
		}
		return s;
	}
	
	private int calDiff(String x, String y) {
		int sum = 0;
		for (int i = 0;i < x.length();i++) {
			if (x.charAt(i) != y.charAt(i)) {
				sum++;
			}
		}
		return sum;
	}
}

解法二：

异或位运算-Java内置函数

异或运算的特性，如果两个bit同为1，或者同为0，那么它们异或的结果就是0，否则就是1.

因此，可以将两个数做异或运算，然后求出这个结果的二进制里面总共有多少个1就可以了。

Java

1
2
3
4
public int hammingDistance(int x, int y) {
		int xor = x ^ y;
		return Integer.bitCount(xor);
	}

解法三：

异或位运算-位运算求1的个数

采用布赖恩·克尼根位计数算法的基本思想。该算法使用特定比特位和算术运算移除等于 1 的最右比特位。

当我们在 number 和 number-1 上做 AND 位运算时，原数字 number 的最右边等于 1 的比特会被移除。

Java

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

解法四：

异或位运算-移位

为了计算等于 1 的位数，可以将每个位移动到最左侧或最右侧，然后检查该位是否为 1。

Java

1
2
3
4
5
6
7
8
9
10
public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int distance = 0;
    while (xor != 0) {
      if (xor % 2 == 1)
        distance += 1;
      xor = xor >> 1;
    }
    return distance;
  }
0%