两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y,计算并返回它们之间的汉明距离。
「汉明距离」是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。--来自百度百科
在解题前,我们先讲几个知识点,解题需要使用到。
位运算就是将数值转换为二进制,按位进行操作。go语言的四个相关操作符如下:
或|
:都是0才是0,否则都是1与&
:都是1才是1,否则都是0^异或
:p | q | P & q | p | q | p ^ q |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 |
两个整数之间的汉明距离是对应位置上数字不同的位数。我们使用异或运算,当且仅当输入位不同时输出为 1。
func hammingDistance(x int, y int) int {
return bits.OnesCount(uint(x ^ y))
}
求x和y的二进制表示中不同位的个数,可以利用异或'^'的性质,相异为1,相同为0,也就是求x^y的二进制表示中,1的个数
func hammingDistance(x int, y int) int {
x = x^y
count := 0
for x > 0 {
//去掉x的二进制表示中,最低位的1,依次循环,直到将所有的1被删除,x为0则退出循环
x &= (x-1)
count += 1
}
return count
}
运行示例
package main
import "fmt"
func main() {
x := 11
fmt.Printf("x: %b\n", x)
y := 20
fmt.Printf("y: %b\n", y)
x = x^y
fmt.Printf("x^y: %b\n", x)
count := 0
for x > 0 {
//去掉x的二进制表示中,最低位的1,依次循环,直到将所有的1被删除,x为0则退出循环
x &= (x-1)
fmt.Printf("循环:%b\n", x)
count += 1
}
fmt.Println("count:", count)
}
运行结果:
x: 01011
y: 10100
x^y: 11111
循环:11110
循环:11100
循环:11000
循环:10000
循环:0
count: 5