【leetcode】【初级算法】【其他2】汉明距离

题目

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

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

示例 1：

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

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnyode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解

方法一：内置位计数功能

class Solution {
    public int hammingDistance(int x, int y) {
        // 方法一：内置计数方法
        return Integer.bitCount(x^y);

    }
}
1
2
3
4
5
6
7

方法二 位移实现位计算

思路：先做同或运算，两个位不相同值等于1，同时为0或1等于0，最后计算通过计算结果中1的个数。即为汉明距离。

class Solution {
    public int hammingDistance(int x, int y) {
        // 方法二 位移实现位计数 
        int s=x^y,ret=0;
        while(s!=0){
            ret+=s&1;
            s>>=1;
        }
        return ret;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12

方法三 Brian Kernihan 算法

这个方法就是结合用到了统计二进制中1的个数的优化算法，先做两数同或操作得到一串二进制（里面是1的个数就是汉名距），再用优化算法：n&=（n-1）直到n==0统计操作次数就可以得到1的个数

class Solution {
    public int hammingDistance(int x, int y) {
        // 方法二 位移实现位计数 
        int s=x^y,ret=0;
        while(s!=0){
            s&=(s-1);
            ret++;
        }
        return ret;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12