[数据结构与算法]461. 汉明距离、Leetcode的Go实现

博客主页：🏆看看是李XX还是李歘歘?🏆

🌺每天不定期分享一些包括但不限于计算机基础、算法、后端开发相关的知识点，以及职场小菜鸡的生活。🌺

💗点关注不迷路，总有一些📖知识点📖是你想要的💗

??今天的内容是? ? ?Leetcode? ? 461. 汉明距离、Leetcode的Go实现? ? ???💻💻💻

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

提示：

0 <=?x, y <= 231 - 1

模拟：进制转换，逐位对比。

func hammingDistance(x int, y int) int {
    // 进制转换
    x1,y1 := tenToTwo(x),tenToTwo(y)
    // 补齐差位
    xLen,yLen := len(x1),len(y1)
    if xLen<yLen {
        dif := make([]int,yLen-xLen)
        x1 = append(x1,dif...)
    } else if xLen>yLen{
        dif := make([]int,xLen-yLen)
        y1 = append(y1,dif...)
    }
    // 遍历对比
    res := 0
    for i:=0;i<len(x1);i++{
        if x1[i]!=y1[i] {
            res++
        }
    }
    return res
}
func tenToTwo(a int) []int {
    res := make([]int,0)
    for a!=0 {
        res = append(res,a%2)
        a=a/2
    }
	return res
}

位运算+移位查询：先将两个数字进行亦或运算（参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为 1），再遍历亦或后的数字1的个数【使用x&1来计算最后一位是否为1，之后利用右移操作将最后一位删除】

func hammingDistance(x int, y int) int {
    x = x^y
    res := 0
    for x > 0 {
        if x&1==1 {
            res++
        }
        x = x >> 1
    }
    return res
}

位运算+内置函数：先将两个数字进行亦或运算（参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为 1），再算出亦或后的数字1的个数【内置函数：bits.OnesCount()】；

func hammingDistance(x int, y int) int {
    x = x^y
    return bits.OnesCount(uint(x))
}