Go 语言实现汉明距离（Hamming Distance）算法详解与源码

• rune 切片处理 Unicode
• 位运算 ^
• & 运算
• 循环控制
• error 返回机制

实现思路

本项目实现三种版本：

第一种：字符串汉明距离

步骤：

1. 转换为 rune 切片
2. 判断长度是否相等
3. 逐个比较
4. 统计不同数量

第二种：整数版本（普通位统计）

步骤：

1. x ^ y
2. 循环右移统计 1

第三种：优化整数版本（Brian Kernighan）

步骤：

1. x ^ y
2. 使用 n = n & (n - 1)
3. 每次消除一个 1
4. 统计次数

代码实现

// =============================================
// 文件：main.go
// =============================================
package main

import (
	"errors"
	"fmt"
)

// =============================================
// 方法一：字符串版本（支持 Unicode）
// =============================================
// HammingDistanceString 计算两个字符串的汉明距离
// 参数：两个字符串
// 返回：距离值，错误信息
func HammingDistanceString(s1, s2 string) (int, error) {
	// 转换为 rune 切片，支持 Unicode
	r1 := []rune(s1)
	r2 := []rune(s2)
	// 长度必须相等
	if len(r1) != len(r2) {
		return 0, errors.New("两个字符串长度必须相等")
	}
	distance := 0
	// 逐字符比较
	for i := 0; i < len(r1); i++ {
		if r1[i] != r2[i] {
			distance++
		}
	}
	return distance, nil
}

// =============================================
// 方法二：整数版本（普通统计法）
// =============================================
// HammingDistanceInt 普通位统计版本
func HammingDistanceInt(x, y int) int {
	// 异或运算
	n := x ^ y
	count := 0
	// 统计二进制中 1 的个数
	for n > 0 {
		if n&1 == 1 {
			count++
		}
		n >>= 1
	}
	return count
}

// =============================================
// 方法三：整数版本（优化 Brian Kernighan）
// =============================================
// HammingDistanceOptimized 优化版本
func HammingDistanceOptimized(x, y int) int {
	n := x ^ y
	count := 0
	// 每次消除一个 1
	for n != 0 {
		n = n & (n - 1)
		count++
	}
	return count
}

// =============================================
// 主函数测试
// =============================================
func main() {
	fmt.Println("====== 字符串版本测试 ======")
	d1, err := HammingDistanceString("karolin", "kathrin")
	if err != nil {
		fmt.Println("错误：", err)
	} else {
		fmt.Println("汉明距离：", d1)
	}
	d2, err := HammingDistanceString("1011101", "1001001")
	if err != nil {
		fmt.Println("错误：", err)
	} else {
		fmt.Println("汉明距离：", d2)
	}
	fmt.Println("\n====== 整数版本测试 ======")
	x := 1
	y := 4
	fmt.Println("普通版本汉明距离：", HammingDistanceInt(x, y))
	fmt.Println("优化版本汉明距离：", HammingDistanceOptimized(x, y))
}

代码解读

1. HammingDistanceString

作用：

• 计算两个字符串的汉明距离
• 支持 Unicode
• 若长度不同返回错误 适合文本比较场景。

2. HammingDistanceInt

作用：

• 计算两个整数的汉明距离
• 使用普通位统计法
• 时间复杂度 O(位数) 适合教学理解。

3. HammingDistanceOptimized

作用：

• 使用 Brian Kernighan 优化算法
• 每次消除一个 1
• 效率更高 适合高性能场景。

总结

本项目系统实现了三种汉明距离算法版本，并详细讲解其原理。

我们掌握了：

• 汉明距离定义
• 异或运算原理
• 位统计方法
• Brian Kernighan 优化算法
• Unicode 安全字符串处理

算法复杂度：

• 字符串版本：O(n)
• 整数普通版：O(位数)
• 优化版：O(1 的个数)

在工程实践中，推荐使用优化版本。

常见问题

Q1：为什么字符串长度必须相等？

汉明距离定义前提是等长字符串。

Q2：整数版本为什么使用异或？

因为： 相同位 → 0 不同位 → 1

Q3：优化算法为什么更快？

因为循环次数等于 1 的个数，而不是位数。

Q4：可以用于大整数吗？

可以使用 math/big 实现。

扩展方向

1. 使用 math/big 实现大整数汉明距离

2. GPU 并行优化

用于图像相似度批量计算。

3. 应用于感知哈希（pHash）

比较图片相似度。

4. 批量计算优化

• 使用位运算批处理
• 使用 SIMD 指令