汉明距离

2022-01-17

Hamming distance 计算两个相同字符串之间对应位置不同字符的个数。

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数

汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。

汉明距离是以理查德·卫斯里·汉明的名字命名的，汉明在误差检测与校正码的基础性论文中首次引入这个概念。在通信中累计定长二进制字中发生翻转的错误数据位，所以它也被称为信号距离。

汉明距离更多的用于信号处理，表明一个信号变成另一个信号需要的最小操作（替换位），实际中就是比较两个比特串有多少个位不一样，简洁的操作时就是两个比特串进行异或之后包含1的个数。

汉明距离在图像处理领域也有着广泛的应用，是比较二进制图像非常有效的手段。计算一个数字的比特位包含1的个数有个小技巧：value &= value - 1这个运算的结果就是把value最后一个1去掉，循环进行运算直到value等于0（所有的1都被去掉）就可以知道vaule拥有多少个1了。

其在包括信息论、编码理论、密码学等领域都有应用。但是，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离等算法。

版权声明：本文为CSDN博主「Yongqiang Cheng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/chengyq116/article/details/113487493

//============================================================================
// Name        : Hamming distance
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

int hamming_distance(const unsigned int x, const unsigned int y)
{
	int dist = 0;
	unsigned int val = x ^ y;

	// Count the number of bits set.
	while (val != 0)
	{
		// A bit is set, so increment the count and clear the bit.
		dist++;
		// val &= val - 1;
		val = val & (val - 1);
	}

	// Return the number of differing bits.
	return dist;
}


int main()
{
	unsigned int x = 1;
	unsigned int y = 4;

	int dist = hamming_distance(x, y);

	printf("dist = %d.\n", dist);

	return 0;
}