64. 海明距離(Hamming Distance)

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/hamming-distance.html

【介紹】

在信息領域，兩個長度相等的字符串的海明距離是在相同位置上不同的字符的個數，也就是將一個字符串替換成另一個字符串需要的替換的次數。

例如：

xxxxyy和xxxxzz的海明距離是2；

111100 和 111111 的海明距離是2；

對於二進制數字來說，海明距離的結果相當於a^b結果中1的個數。

【字符串】

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28   /*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/5/30
*/
// hamming distance of two strings
unsigned hamdist(const char *str1, const char *str2)
{
    // aaabb aaacc
    if (str1 == NULL || str2 == NULL)
        return 0;

    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if (len1 != len2)
        return 0;

    unsigned dist = 0;
    while(*str1 && *str2)
    {
        dist += (*str1 != *str2) ? 1 : 0;
        str1++;
        str2++;
    }
    return dist;
}

【數字】

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21   /*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/5/30
*/
// hamming distance of two integer 0-1 bits
unsigned hamdist(unsigned x, unsigned y)
{
    //  11111 11100
    unsigned dist = 0, val = x ^ y; // XOR

    // Count the number of set bits
    while(val)
    {
        ++dist;
        val &= val - 1;
    }

    return dist;
}

【參考】

http://blog.csdn.net/fuyangchang/article/details/5637464

http://en.wikipedia.org/wiki/Hamming_distance

http://my.oschina.net/u/1401481/blog/223223

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/hamming-distance.html