LeetCode-Day23 (C#) 461. 汉明距离

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

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

注意：
0 ≤ x, y < 2³¹.

思路
汉明距离广泛应用于多个领域。在编码理论中用于错误检测，在信息论中量化字符串之间的差异。

两个整数之间的汉明距离是对应位置上数字不同的位数。

根据以上定义，提出一种 XOR 的位运算，当且仅当输入位不同时输出为 1。

image.png

计算 x 和 y 之间的汉明距离，可以先计算 x XOR y，然后统计结果中等于 1 的位数。

现在，原始问题转换为位计数问题。位计数有多种思路，将在下面的方法中介绍。

方法二：移位
思路

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

更准确的说，应该进行逻辑移位，移入零替换丢弃的位。

image.png

这里采用右移位，每个位置都会被移动到最右边。移位后检查最右位的位是否为 1 即可。检查最右位是否为 1，可以使用取模运算（i % 2）或者 AND 操作（i & 1），这两个操作都会屏蔽最右位以外的其他位。

public class Solution {
    public int HammingDistance(int x, int y) {
        int xor = x ^ y;
        int distance = 0;
        while(xor != 0){
            if(xor % 2 ==1) distance++;
            xor = xor >> 1;
        }
        return distance;
    }
}