首页 > 代码库 > 461. Hamming Distance（leetcode）

461. Hamming Distance（leetcode）

2024-11-14 13:30:02   203人阅读

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 2^31.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ?   ?

The above arrows point to positions where the corresponding bits are different.

　　

汉明距离

是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离

 

这道题通俗的讲是两个数的二进制之间的不同之处有几个，即异或运算后结果中1的个数。

很容易，我们可以写出以下代码：

 

public int hammingDistance(int x, int y) {
    int xor = x ^ y, count = 0;
    for (int i=0;i<32;i++) count += (xor >> i) & 1;
    return count;
}

对x、y两个整数进行异或运算，得到结果xor，接下来计算xor中1的个数，即可算得汉明距离。

对xor右移，然后对该二进制数与1运算（得到最右边的那个数字是否为1），循环直到结束。

 

 

更简单的，基于java自带的Integer.bitCount（int i）函数，可以用一行代码解决问题：

public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

 

我们可以来看一下bitCount函数的原理：

 

    public static int bitCount(int i) {  
        // HD, Figure 5-2  
        i = i - ((i >>> 1) & 0x55555555);  
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);  
        i = (i + (i >>> 4)) & 0x0f0f0f0f;  
        i = i + (i >>> 8);  
        i = i + (i >>> 16);  
        return i & 0x3f;  
    }

 

　　二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。

 

　　第一行是计算每两位中的 1 的个数 , 并且用该对应的两位来存储这个个数 。

　　如 : 01101100 -> 01011000 , 即先把前者每两位分段 01 10 11 00 , 分别有 1 1 2 0 个 1, 用两位二进制数表示为 01 01 10 00, 合起来为 01011000.

 

　　第二行是计算每四位中的 1 的个数 , 并且用该对应的四位来存储这个个数。

　　如 : 01101100 经过第一行计算后得 01011000 , 然后把 01011000 每四位分段成 0101 1000 , 段内移位相加 : 前段01+01 =10 , 后段 10+00=10, 分别用四位二进制数表示为 0010 0010, 合起来为 00100010 .


　　下面的各行以此类推 , 分别计算每 8 位 ,16 位 ,32 位中的 1 的个数 .


　　将 0x55555555, 0x33333333, 0x0f0f0f0f 写成二进制数的形式就容易明白了 .

 

[bitCount函数原理参考http://15838341661-139-com.iteye.com/blog/1642525]

 

461. Hamming Distance（leetcode）


联系
我们