c语言练习题80：汉明距离

汉明距离

题⽬描述：

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

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

⽰例 1：

输⼊：x = 1, y = 4

输出：2

解释：

1 (0 0 0 1)

4 (0 1 0 0)

       ↑     ↑

• ⽰例 2：

输⼊：

x = 3, y = 1

输出：1

解法（位运算）：

异或（^）运算：将两个⼆进制数按位进⾏⽐较，若相应位不同则该位结果为1，否则结果为0。

例 如，

对于⼆进制数1010和1101，它们的异或结果为0111。

本题利⽤异或（^）运算符将两数异或后，求得其中1的个数即可。

为了更快地统计某个数 r 中1的个数，可以使⽤ r&(r-1) 运算，它可以直接将 r 中最右边的1变为 0。这是因为 r-1 操作将r的最右边的1变为0，并将1后⾯的0变为1，所以 r 和 r-1 在这些位上⼀ 定有其中⼀个含有0。

例如：（与c语言练习题30相似）

r=110100 ， r-1=110011 ， r&(r-1)=110000 。

因此，进⾏按位与运算后，结果相当于将 r 最右边的1变为0。接下来，我们只需要记录 r 不为0时 r&(r-1) 可以操作的次数即可。

算法思路：

1. 定义⼀个变量 r ，将其初始化为 x 和 y 的异或值；

2. 定义⼀个变量 n ，将其初始化为0；

3. 当 r 不为0时， n 的值加⼀并执⾏⼀次r=r&(r-1)操作。

4. 返回 n 。

int hammingDistance(int x, int y) {
	//⾸先进⾏两数异或运算求得r
	int r = x ^ y;
	int n = 0;
	//当r不为0时记录⼀次并且执⾏⼀次r&(r-1)操作
	while (r) {
		n++;
		r = r & (r - 1);
	}
	return n;
}