题目描述 LeetCode 461
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 < 231.
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.
中文描述
在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
本题以汉明距离为载体，给定两个十进制数，然后把十进制转化为各自二进制形式，求两个二进制之间的汉明距离。
解题思路
- 定义一个子函数来求十进制的二进制形式，二进制形式用数组来保存，并返回各自的长度。
- 既然二进制串，肯定有的长，有的短（如 十进制的 10 转化为二进制为 1010， 十进制的 2 转化为二进制为 10），所以要分三种情况讨论:
- 第一，x 比 y 的二进制长度短。
- 第二， x 比 y 的二进制长度长。
- 第三， x 和 y 的二进制长度相等。
- 对于长短不等的情况，先计算在短的长度内汉明距离，然后再计算长的范围内汉明距离。
- 例如，x 比 y 短，则在 0 ~ x_length 范围内计算两者汉明距离（比较两者数字不同的数目），然后在 x_length ~ y_length 的范围内在 y 二进制的基础上计算汉明距离（计算在 x_length ~ y_length 范围内为 1 的数目，因为 x 在此范围内肯定为 0）。
- 对于 x 和 y 长度相等的情况，直接在 0 ~ x_length 的范围内进行比较即可（比较两者数字不同的数目）。
C语言实现
# include <stdio.h>
// 十进制转化为二进制，用数组保存，并返回二进制长度
int shijinzhizhuanerjinzhi(int x, int *xx)
{
int length = 0;
while(x/2 != 0)
{
*(xx + length) = x%2;
x = x/2;
length ++;
}
*(xx + length) = x;
return length + 1;
}
// 计算两个十进制的汉明距离，并返回
int hammingDistance(int x, int y)
{
int i;
int sum = 0; // 保存汉明距离
int xx[32]; // 保存 x 的二进制
int yy[32]; // 保存 y 的二进制
int x_length = 0; // 保存 x 的二进制长度
int y_length = 0; // 保存 y 的二进制长度
// 调用子函数 十进制转化为二进制，用数组保存，并且返回十进制的二进制长度
x_length = shijinzhizhuanerjinzhi(x, xx);
y_length = shijinzhizhuanerjinzhi(y, yy);
// 第一，x 比 y 的二进制长度短。
if(x_length < y_length)
{
for( i = 0; i < x_length; i ++)
{
if(xx[i] != yy[i])
{
sum ++ ;
}
}
for( i = x_length; i < y_length; i ++)
{
if(yy[i] == 1)
{
sum ++ ;
}
}
}
else if(x_length > y_length) //x 比 y 的二进制长度长。
{
for( i = 0; i < y_length; i ++)
{
if(xx[i] != yy[i])
{
sum ++ ;
}
}
for( i = y_length; i < x_length; i ++)
{
if(xx[i] == 1)
{
sum ++ ;
}
}
}
else // 第三， x 和 y 的二进制长度相等。
{
for( i = 0; i < x_length; i ++)
{
if(xx[i] != yy[i])
{
sum ++ ;
}
}
}
return sum;
}
main()
{
int x = 1;
int y = 4;
printf("\n\n%d\n\n", hammingDistance(x, y));
}
执行效果
运行结果
思考
- 做题发现 C 语言能调用的函数真是少，映像中只有 strlen,strcmp,strcat 寥寥无几，相比 python, java, C++ 真是太少了，不过在前期这样也挺好，可以锻炼编程能力，毕竟不能太依赖库函数。 貌似这就是 LeetCode 上面C语言程序比其他语言程序长的原因。
