汉明距离

位运算

说明

异或后统计不同的二进制位；时间与机器字长度有关。

分析

异或会在两个整数不同的位上产生 1。循环执行 x &= x−1，每次清除最低的一个置位，所以循环次数等于汉明距离。

图解推演

1011 XOR 0010=1001，只有两位不同。1001 与 1000 按位与后剩 1000，再与 0111 按位与得到 0，执行两轮，所以距离为 2。这计算的是固定位宽二进制表示的差异，不是十进制数字的差异。

查看图表代码

适用前提与边界

比较很长的二进制串时，可以分块处理并累加每块的置位数。

示例输入与调用

fmt.Println(HammingDistance(0b1011, 0b0010))

运行输出

2

完整 Go 示例

package main

import "fmt"

func HammingDistance(a, b uint) int {
	x := a ^ b
	count := 0
	for x != 0 {
		x &= x - 1
		count++
	}
	return count
}

func main() {
	fmt.Println(HammingDistance(0b1011, 0b0010))
}