当前位置：网站首页 > 创业 > 正文

C++：汉明距离的实现

张子豪 2025-10-12 04:30 1

绪：

汉明距离是一种权衡特征距离的计较方式，

其本家儿要思惟是找到两个特征之间的差别巨细，也可以说是相似性；

汉明距离是以理查德·卫斯里·汉明的名字定名的，汉明在误差检测与校正码的根本性论文中初次引入这个概念。

用来权衡2个二进制码字之间的相似水平的。

东西/原料

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
汉明距离的应用：
汉明距离本家儿要应用在通信编码范畴上，用于拟定可纠错的编码系统。
在机械进修范畴中，汉明距离也经常被用于作为一种距离的怀抱体例；