伊莉討論區

標題: leetcode 461.hammingDistance [打印本頁]

---

作者: 阿次阿    時間: 2017-3-13 05:26 PM     標題: leetcode 461.hammingDistance

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: CoNsTaRwU    時間: 2017-3-14 06:18 PM

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: 阿次阿    時間: 2017-3-15 05:21 PM

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: CoNsTaRwU    時間: 2017-3-16 11:39 PM

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: ren1244    時間: 2017-3-17 12:16 AM



先解釋一下問題在哪裡：

當n=31時，「x/(int)pow(2.0,n)」會先計算2[sup]31[/sup]=2147483648。但是對32bit的int而言，所能儲存的最大值是2147483647。把2147483648轉換為最大只能儲存2147483647的int原本就有問題。也就是所謂的溢位了。不同編譯器處理方式可能不一樣。

既然題目已經說x,y都會小於2[sup]31[/sup]，那麼所有的x,y用2[sup]31[/sup]做整數除法必然都為0。也就是說我們根本不需要檢查n=31的狀況，從n=30開始檢查即可。

只要把for迴圈的31改成30問題就可以解決了。

(後面是其他補充)

面對這種問題，其實不需要用到pow函數。
如果反向從低位向高位來比對，就可以只用整數方式來處理：

1. int hammingDistance(int x, int y)
   
2. {
   
3.     int n;
   
4.     int key=0;
   
5.     for(n=0;n<31;++n)
   
6.     {
   
7.         if(x%2 != y%2)
   
8.             ++key;
   
9.         x=x/2;
   
10.         y=y/2;
    
11.     }
    
12.     return key;
    
13. }

複製代碼

寫到這邊，概念上還停留在十進位整數。
如果可以理解整數是以二進位儲存，並能活用位元運算，下面這段程式碼也是做同樣的事情
(一般來說位元運算的速度比加減乘除快)

1. int hammingDistance(int x,int y)
   
2. {
   
3.     int k=0;
   
4.     int t;
   
5.     for(t=x^y;t;t>>=1)
   
6.         if(t&1)
   
7.             ++k;
   
8.     return k;
   
9. }

複製代碼

---

作者: 阿次阿    時間: 2017-3-17 10:03 PM

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: gitlab    時間: 2017-5-4 09:53 PM

其實就是計算 x xor y 的二進位表示法裡面有多少1

提供一個「二進位表示法裡面有多少1」很有名的作法

int a = x ^ y;
int cnt = 0;
while( a ){
   cnt += 1;
   a &= a-1;
}
return cnt;

---

歡迎光臨 伊莉討論區 (http://www01.eyny.com/)

Powered by Discuz!