[思路]LeetCode Problems- 461. Hamming Distance

有鑑於上次按隨機鍵出來的題目難度特高,花了不少心思,
並且上週去成大一個禮拜沒碰到程式許久,
我決定這次來解決一些較簡單的題目,
並嘗試不用C++而用C語言來完成

這次練習的題目是Hamming Distance,題目原文如下:

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)在通訊領域裡是頗重要的編碼應用,個人最早是在學習通道編碼的Viterbi演算法中碰到的.

在Viterbi演算法中需要透過編碼器的格狀架構找出一條最短路徑，找出擁有「最大可能性」路徑的方法,而這就需要應用到漢明距離.最簡單的解釋就是位元數不同的數目總和

例如：(wiki)

• 1011101與1001001之間的漢明距離是2
• 2143896與2233796之間的漢明距離是3

跟先前寫過的題目來比,這一題的邏輯脈絡就清楚許多,可分成三個步驟:

1.十進位轉換成二進位

2.轉換後資料存成字串或陣列

3.比對兩個字串或陣列的內容

首先要來處理的就是位制轉換問題,十進位轉換成二進位的方法如下所示:

簡言之 這演算法有兩個重要skill:

1.取得餘數(1或者是0)

2.針對除法所得到的商數繼續做除法

有了這兩個概念後我們就可以用FOR迴圈來實現這個轉換問題

已知輸入的十進位變數是 x , 則

     int k1;

    for (int i=0; i<31; i++){   //重複31次代表二進位元最大個數(題目限制)

        k1 = x % 2;   //使用%運算子取得餘數並更新k1變數

       X1[i]=k1;   //餘數存入陣列中

       x /= 2;    //算術指派運算子,即是把原變數用商取代掉

                      //意思即為  x=x / 2

    }

接著就是要取得轉換後的結果,

我一開始還在想說是要用普通陣列還是要把int數值轉換成字串來儲存,後來發覺就算存成字串也沒有方便的函數比較內容,用strcmp()或是strncmp()也只是找出位置後就停止搜尋,還沒有直接用if條件式來比較的方便:

int X1[31] = {0}; //預設元素都是0的陣列

int Y1[31] = {0};

//轉換完後比對資料

 int count=0; //計數

    for (int l=0;l<31;l++)

    {        

        if (X1[l]!=Y1[l]) //若發覺有不同數值

        {       count++;    //計數+1   }           

    }

最後的count就是Hamming Distance了

寫完後按送出鍵.....一次就成功~!!!