【Leetcode】汉明距离

汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)

• 解法一：

class Solution1 {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y); //x ^ y异或：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0
    }
}

• 解法二：

class Solution2 {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;//s & 1: s的值和1按二进制位与 若s的最低位为1，结果为1；否则为0
            s >>= 1;
        }
        return ret;
    }
}

• 解法三：

我们可以使用 Brian Kernighan算法进行优化，具体地，该算法可以被描述为这样一个结论：
记 f(x) 表示 x 和 x-1 进行与运算所得的结果（即f(x)=x & (x−1)），那么 f(x)恰为 x删去其二进制表示中最右侧的 1的结果。

class Solution3 {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s-1;
            ret++;
        }
        return ret;
    }
}