461. 汉明距离

描述

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

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

注意：

$0 ≤ x, y < 2^{31}.$

示例:

输入: x = 1, y = 4

输出: 2

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

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

来源：力扣（LeetCode）
链接：461. Hamming Distance

解题思路

本题的题意比较明确，可以比较方便地转换为我们的解题思路，首先就是对两个整数进行异或，然后统计异或以后得到的整数二进制当中1的个数。

异或操作就不多说了，各个语言都有自己的操作符，C语言是^。

重点是如果统计异或所得整数当中1的个数。

本文主要参考算法-求二进制数中1的个数中介绍的前面两种算法进行代码实现。

普通法

我总是习惯叫普通法，因为我实在找不到一个合适的名字来描述它，其实就是最简单的方法，有点程序基础的人都能想得到，那就是移位+计数，很简单，不多说了，直接上代码，这种方法的运算次数与输入n最高位1的位置有关，最多循环32次。

具体代码实现见解法一。

快速法

这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0。为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。

具体代码实现见解法二。

代码

解法一

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

解法二

int hammingDistance(int x, int y)
{
    int xor = x^y;
    
    int result = 0;
    
    while(xor)
    {
        result++; 
        xor &= (xor - 1);
    }
    
    return result;
}

参考

• 算法-求二进制数中1的个数