題目描述 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 < 2³¹.

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.

中文描述

在信息論中，兩個(gè)等長(zhǎng)字符串之間的漢明距離（英語(yǔ)：Hamming distance）是兩個(gè)字符串對(duì)應(yīng)位置的不同字符的個(gè)數(shù)。換句話說，它就是將一個(gè)字符串變換成另外一個(gè)字符串所需要替換的字符個(gè)數(shù)。

本題以漢明距離為載體，給定兩個(gè)十進(jìn)制數(shù)，然后把十進(jìn)制轉(zhuǎn)化為各自二進(jìn)制形式，求兩個(gè)二進(jìn)制之間的漢明距離。

解題思路

• 定義一個(gè)子函數(shù)來求十進(jìn)制的二進(jìn)制形式，二進(jìn)制形式用數(shù)組來保存，并返回各自的長(zhǎng)度。
• 既然二進(jìn)制串，肯定有的長(zhǎng)，有的短（如 十進(jìn)制的 10 轉(zhuǎn)化為二進(jìn)制為 1010， 十進(jìn)制的 2 轉(zhuǎn)化為二進(jìn)制為 10），所以要分三種情況討論:
  • 第一，x 比 y 的二進(jìn)制長(zhǎng)度短。
  • 第二， x 比 y 的二進(jìn)制長(zhǎng)度長(zhǎng)。
  • 第三， x 和 y 的二進(jìn)制長(zhǎng)度相等。
• 對(duì)于長(zhǎng)短不等的情況，先計(jì)算在短的長(zhǎng)度內(nèi)漢明距離，然后再計(jì)算長(zhǎng)的范圍內(nèi)漢明距離。
  • 例如，x 比 y 短，則在 0 ~ x_length 范圍內(nèi)計(jì)算兩者漢明距離（比較兩者數(shù)字不同的數(shù)目），然后在 x_length ~ y_length 的范圍內(nèi)在 y 二進(jìn)制的基礎(chǔ)上計(jì)算漢明距離（計(jì)算在 x_length ~ y_length 范圍內(nèi)為 1 的數(shù)目，因?yàn)?x 在此范圍內(nèi)肯定為 0）。
• 對(duì)于 x 和 y 長(zhǎng)度相等的情況，直接在 0 ~ x_length 的范圍內(nèi)進(jìn)行比較即可（比較兩者數(shù)字不同的數(shù)目）。

C語(yǔ)言實(shí)現(xiàn)

# include <stdio.h>

// 十進(jìn)制轉(zhuǎn)化為二進(jìn)制，用數(shù)組保存，并返回二進(jìn)制長(zhǎng)度
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;
}

// 計(jì)算兩個(gè)十進(jìn)制的漢明距離，并返回
int hammingDistance(int x, int y) 
{
    int i;
    int sum = 0;       // 保存漢明距離
    int xx[32];        // 保存 x 的二進(jìn)制
    int yy[32];        // 保存 y 的二進(jìn)制
    int x_length = 0;  // 保存 x 的二進(jìn)制長(zhǎng)度
    int y_length = 0;  // 保存 y 的二進(jìn)制長(zhǎng)度
    
    // 調(diào)用子函數(shù) 十進(jìn)制轉(zhuǎn)化為二進(jìn)制，用數(shù)組保存，并且返回十進(jìn)制的二進(jìn)制長(zhǎng)度
    x_length = shijinzhizhuanerjinzhi(x, xx);
    y_length = shijinzhizhuanerjinzhi(y, yy);

    // 第一，x 比 y 的二進(jìn)制長(zhǎng)度短。
    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 的二進(jìn)制長(zhǎng)度長(zhǎng)。
    {
        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 的二進(jìn)制長(zhǎng)度相等。
    {
        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));
}

執(zhí)行效果

運(yùn)行結(jié)果

思考

• 做題發(fā)現(xiàn) C 語(yǔ)言能調(diào)用的函數(shù)真是少，映像中只有 strlen,strcmp,strcat 寥寥無幾，相比 python, java, C++ 真是太少了，不過在前期這樣也挺好，可以鍛煉編程能力，畢竟不能太依賴庫(kù)函數(shù)。 貌似這就是 LeetCode 上面C語(yǔ)言程序比其他語(yǔ)言程序長(zhǎng)的原因。