[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 < 2^31.

**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了

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