C++：汉明距离的实现

1、汉明距离定义：

从二进制上讲是：两个等长字符串的二进制对应位不相同的位个数；

例如：

“toned”和”roses”的汉明距离是3。

1011101和1001001的汉明距离是2。

2173896和2233796的汉明距离是3。

2、汉明距离的意义：

对于二进制字符串ａ和ｂ来说，

汉明距离等于a^b中１的数目，又叫做汉明权重。

长度为ｎ的二进制字符串通过汉明距离构成了一个度量空间(metric space)，

称汉明立方(Hamming Cube)；

下图给出了在hypercube中：

0100→1001 (红色)的汉明距离是 3;

0110→1110 (蓝色)的汉明距离是 1；

3、汉明距离实现思路：

①将两个给定的数进行异或(^)运算后保存在变量a中，

则汉明距离就是二进制a中1的个数；

②当a不为0时，和0x01进行按位与(&)运算，如果结果为1，则统计变量加一

③将a右移一位，重复第02步

4、代码：

//汉明距离计算

int hamDist(char *a, char *b)

{

       int dist = 0;

       while (*a && *b)

       {

              dist += (*a != *b)?1:0;//异或

              *a++;

              *b++;

       }

       return dist;

}

int main()

{

       char *a,*b;//字符指针

       a = "0000100100000001";

       b = "0010100001100100";

       int dist = hamDist(a,b);

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

       getchar();

       return 0;

}

5、计算两个整数的二进制汉明距离；

Wegner (1960)给出了一种计算汉明权重（即计算给定整数的二进制表示中１的个数）的算法，通过反复查找并消除最低的非零位来实现。

基于此使用Ｃ语言实现的计算汉明距离的算法如下：

//while循环的次数就是汉明距离；

//计算汉明距离

unsigned int value = a^b;

int GetHammingWeight(unsigned int value)

{

       if(value == 0)

              return 0;

       int a = value;

       int b = value -1;

       int c = 0;

       int count = 1;

       while(c = a & b)

       {

              count++;

              a = c;

              b = c-1;

       }

       return count;

}

6、汉明距离的应用：

汉明距离主要应用在通信编码领域上，用于制定可纠错的编码体系。

在机器学习领域中，汉明距离也常常被用于作为一种距离的度量方式；