力扣题目:
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y,计算并返回它们之间的汉明距离。
「汉明距离」是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。--来自百度百科
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/hamming-distance
在解题前,我们先讲几个知识点,解题需要使用到。
golang的异或符
位运算就是将数值转换为二进制,按位进行操作。go语言的四个相关操作符如下:
或|
:都是0才是0,否则都是1与&
:都是1才是1,否则都是0^异或
:- 二元:a ^ b : 对应位的值相同则为0,不同则为1
- 一元:^a : 按位取反 1变0,0变1
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 |
移位运算:
- number >> 4 将数字转为二进制,整体向右移动4位,再将结果转为十进制;
- number << 4 数字转为二进制,整体向左移动4位,再将结果转为十进制
解题
1. 内置位计数功能
两个整数之间的汉明距离是对应位置上数字不同的位数。我们使用异或运算,当且仅当输入位不同时输出为 1。
代码语言:javascript复制func hammingDistance(x int, y int) int {
return bits.OnesCount(uint(x ^ y))
}
2. 异或计数
求x和y的二进制表示中不同位的个数,可以利用异或'^'的性质,相异为1,相同为0,也就是求x^y的二进制表示中,1的个数
代码语言:javascript复制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
}
运行示例
代码语言:javascript复制package main
import "fmt"
func main() {
x := 11
fmt.Printf("x: %bn", x)
y := 20
fmt.Printf("y: %bn", y)
x = x^y
fmt.Printf("x^y: %bn", x)
count := 0
for x > 0 {
//去掉x的二进制表示中,最低位的1,依次循环,直到将所有的1被删除,x为0则退出循环
x &= (x-1)
fmt.Printf("循环:%bn", x)
count = 1
}
fmt.Println("count:", count)
}
运行结果:
代码语言:javascript复制x: 01011
y: 10100
x^y: 11111
循环:11110
循环:11100
循环:11000
循环:10000
循环:0
count: 5