頁:
[1]
leetcode 461.hammingDistance
本帖最後由 阿次阿 於 2017-3-13 05:27 PM 編輯小弟在做這題，要算兩字的漢明距離，0 ≦ x, y < 2^31
int hammingDistance(int x, int y) {
int n;
int key=0;
for(n=31;n>=0;n--){
if((x/(int)pow(2.0,n))==1){
if((y/(int)pow(2.0,n))==1){
x=x%(int)pow(2.0,n);
y=y%(int)pow(2.0,n);
}
else if((y/(int)pow(2.0,n))==0){
x=x%(int)pow(2.0,n);
y=y;
key=key+1;
}
}
else if((x/(int)pow(2.0,n))==0){
if((y/(int)pow(2.0,n))==1){
x=x;
y=y%(int)pow(2.0,n);
key=key+1;
}
else if((y/(int)pow(2.0,n))==0){
x=x;
y=y;
}
}
}
return key;
}
小弟自己試試都成功，答案都對
可是我在網路上寫，當x跟y都是2147483647時
他說我跑出來的答案是1
可是我自己跑就是零阿...還是有哪裡有問題><
請大大幫我明察
感謝
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 未看先猜 int 溢位......
看到你有用 pow，提醒一下 gcc 的 pow 是 builtin function，小心使用
嗯…我猜應該是 pow 丟回 int 的時候溢位了，先試試看把 int 都改 long，ok 了再慢慢修 改完後就過了!
感謝大大
不過為何在網路上不能而我用vs2010就能跑...? 本帖最後由 CoNsTaRwU 於 2017-3-16 11:40 PM 編輯
因為 C 語言雖然會做 type checking，不過在某些(其實超多)地方的行為是不被 type checked 保證的
例如你這裡的 implicit cast long to int 就是其中一種
如果希望編譯器盡他所能在編譯時期幫你找到這些錯誤可以下對應的參數，M$VC 我不瞭解，我自己是喜歡用 clang，我會開 -Wall -Wextra -Weverything -pedantic
本帖最後由 ren1244 於 2017-3-17 12:20 AM 編輯
先解釋一下問題在哪裡：
當n=31時，「x/(int)pow(2.0,n)」會先計算231=2147483648。但是對32bit的int而言，所能儲存的最大值是2147483647。把2147483648轉換為最大只能儲存2147483647的int原本就有問題。也就是所謂的溢位了。不同編譯器處理方式可能不一樣。
既然題目已經說x,y都會小於231，那麼所有的x,y用231做整數除法必然都為0。也就是說我們根本不需要檢查n=31的狀況，從n=30開始檢查即可。
只要把for迴圈的31改成30問題就可以解決了。
(後面是其他補充)
面對這種問題，其實不需要用到pow函數。
如果反向從低位向高位來比對，就可以只用整數方式來處理：int hammingDistance(int x, int y)
{
int n;
int key=0;
for(n=0;n<31;++n)
{
if(x%2 != y%2)
++key;
x=x/2;
y=y/2;
}
return key;
}寫到這邊，概念上還停留在十進位整數。
如果可以理解整數是以二進位儲存，並能活用位元運算，下面這段程式碼也是做同樣的事情
(一般來說位元運算的速度比加減乘除快)int hammingDistance(int x,int y)
{
int k=0;
int t;
for(t=x^y;t;t>>=1)
if(t&1)
++k;
return k;
}...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div> ren1244 發表於 2017-3-17 12:16 AM static/image/common/back.gif
先解釋一下問題在哪裡：
當n=31時，「x/(int)pow(2.0,n)」會先計算2=2147483648。但是對32bit的int而言， ...
強大...受教了
之前在網路上有看到類似您第二種的方法
可是不懂為何直接移位就可以了
現在才知道原來整數是以二進位儲存
總算明白他那樣做的原因了
感謝
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 其實就是計算 x xor y 的二進位表示法裡面有多少1
提供一個「二進位表示法裡面有多少1」很有名的作法
int a = x ^ y;
int cnt = 0;
while( a ){
cnt += 1;
a &= a-1;
}
return cnt;
頁:
[1]