题目

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：

0

≤

x

,

y

<

2

31

0 ≤ x, y < 2^{31}

0≤x,y<231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1 (0 0 0 1)
4 (0 1 0 0)
       ↑    ↑

上面的箭头指出了对应二进制位不同的位置。

题解

我

class Solution {
    public int hammingDistance(int x, int y) {
        int count = 0;
        while(x != 0 || y != 0){
            if(x % 2 != y % 2)
                count++;
            x /= 2;
            y /= 2;
        }
        return count;
    }
}

官方
方法一：内置位计数功能
大多数编程语言都内置了计算二进制表达中 1 的数量的函数。在工程中，我们应该直接使用内置函数。

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

方法二：移位实现位计数
具体地，记

s

=

x

⊕

y

s = x \oplus y

s=x⊕y ，我们可以不断地检查 s的最低位，如果最低位为 1，那么令计数器加一，然后我们令 s 整体右移一位，这样 s 的最低位将被舍去，原本的次低位就变成了新的最低位。我们重复这个过程直到 s=0为止。这样计数器中就累计了 s 的二进制表示中 1 的数量。

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;   // ^异或
        while (s != 0) {
            ret += s & 1;  //检查最低位
            s >>= 1;  // 右移一位
        }
        return ret;
    }
}

方法三：

Brian Kernighan

B

r

i

a

n

K

e

r

n

i

g

h

a

n

\text{Brian Kernighan}Brian Kernighan

Brian KernighanBrianKernighan算法
在方法二中，对于

s

=

(

10001100

)

2

s=(10001100)_2

s=(10001100)2​的情况，我们需要循环右移 8次才能得到答案。而实际上如果我们可以跳过两个1之间的0，直接对1进行计数，那么就只需要循环 3 次即可。
我们可以使用

Brian Kernighan

B

r

i

a

n

K

e

r

n

i

g

h

a

n

\text{Brian Kernighan}Brian Kernighan

Brian KernighanBrianKernighan算法进行优化，具体地，该算法可以被描述为这样一个结论：记 f(x) 表示x和x−1进行与运算所得的结果（即

f

(

x

)

=

x

 

&

 

(

x

−

1

)

f(x)=x~\&~(x-1)

f(x)=x & (x−1)，那么f(x) 恰为x删去其二进制表示中最右侧的1的结果。

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }
}