力扣题461汉明距离

力扣题461汉明距离

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

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

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
          ↑    ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：

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

1.自己的解法：判断两个数的每一位是否相等。

class Solution {
    public int hammingDistance(int x, int y) {
        int count = 0;
        while (x != 0 || y != 0) {
            int num1 = x % 2;//x当前位的数字
            int num2 = y % 2;//y当前位的数字
            if (num1 != num2) {//不相等就加1
                count++;
            } 
            x = x >> 1;//右移x
            y = y >> 1;//右移y
        }
        return count;
    }
}

2.题解：对两个数进行异或运算，然后统计1的数量即可。

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y;//异或运算
        int count = 0;
        while (s != 0) {
            count += s & 1;//判断最低位是不是1
            s >>= 1;//右移，更新最低位
        }
        return count;
    }
}

        Brian Kernighan 算法。对于s=10001100的情况，我们需要循环右移8次才能得到答案。而

      实际上如果我们可以跳过两个1之间的0，直接对1进行计数，那么就只需要循环3次即可。可以

      使用Brian Kernighan 算法进行优化，具体地，该算法可以被描述为这样一个结论：记f(x)表示x

      和x−1进行与运算所得的结果（即f(x)=x & (x−1)），那么f(x)恰为x删去其二进制表示中最右侧

      的1的结果。基于该算法，当我们计算出s=x⊕y，只需要不断让s=f(s)，直到s=0 即可。这样每

      循环一次，s都会删去其二进制表示中最右侧的1，最终循环的次数即为s的二进制表示中1的数

      量。这种算法优化可以跳过0直接统计1的个数。

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

 

题源：力扣