2019独角兽企业重金招聘Python工程师标准>>> hot3.png

发表时间: 2013年1月17日 | 作者: 陈杰斌 | 所属分类: C语言 | 评论: 0 | 浏览: 1376

在庞果网上看到计算两个字符串的汉明距离问题，要求用java实现。自己不熟悉java，就想着用c尝试下。汉明距离就是两个等长字符串对应位置的不同字符的个数。例如：

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

  • 1011101和1001001的汉明距离是2。

  • 2173896和2233796的汉明距离是3。

c语言的实现代码：

1 int hamdist(char *a, char *b)
2 {
3     int dist = 0;
4
5     while (*a && *b) {
6         dist += (*a != *b) ? 1 : 0;
7         *a++;
8         *b++;
9     }
10
11     return dist;
12 }

这里没有考虑两个字符串长度不一致的情况，如果长度不一致则涉及到编辑距离，关于编辑距离维基百科上有相关说明，这里就不介绍了。该方法的执行时间由字符串长度决定，时间复杂度是O(n)。用两个字符串来测试一下：

1 #include <stdio.h>
2
3 int main()
4 {
5     char *a, *b;
6     a = "00001001000001110000000000100001";
7     b = "00101000000101110000010000100001";
8
9     int dist = hamdist(a, b);
10     //输出4
11     printf("%d\n", dist);
12
13     return 0;
14 }

另外如果要计算两个整数的二进制的汉明距离，可以使用如下方法，效率更高。

查看源代码打印帮助

1 int hamdist(int a, int b)
2 {
3     int dist = 0, val = a ^ b;
4     printf("%d\n", val);
5     while (val) {
6         ++dist;
7         val &= val - 1;
8     }
9
10     return dist;
11 }

这边while循环的次数其实就是汉明距离。

小结

汉明距离是以理查德·卫斯里·汉明的名字命名的，有兴趣的朋友可以了解下这位先辈。除了汉明距离，还有汉明重量、汉明码等理论在信息论、编码理论、密码学等领域都有应用。

转载于:https://my.oschina.net/u/1401481/blog/223223