leetcode 461.hammingDistance

阿次阿

小弟在做這題，要算兩字的漢明距離，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);
...

瀏覽完整內容，請先 註冊 或 登入會員

未看先猜 int 溢位......
看到你有用 pow，提醒一下 gcc 的 pow 是 builtin function，小心使用

嗯…我猜應該是 pow 丟回 int 的時候溢位了，先試試看把 int 都改 long，ok 了再慢慢修

阿次阿

改完後就過了!
感謝大大
不過為何在網路上不能而我用vs2010就能跑...?

因為 C 語言雖然會做 type checking，不過在某些(其實超多)地方的行為是不被 type checked 保證的

例如你這裡的 implicit cast long to int 就是其中一種

如果希望編譯器盡他所能在編譯時期幫你找到這些錯誤可以下對應的參數，M$VC 我不瞭解，我自己是喜歡用 clang，我會開 -Wall -Wextra -Weverything -pedantic
...

瀏覽完整內容，請先 註冊 或 登入會員

ren1244

先解釋一下問題在哪裡：

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

既然題目已經說x,y都會小於2³¹...

瀏覽完整內容，請先 註冊 或 登入會員

阿次阿

ren1244 發表於 2017-3-17 12:16 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

先解釋一下問題在哪裡：

當n=31時，「x/(int)pow(2.0,n)」會先計算2=2147483648。但是對32bit的int而言， ...

強大...受教了
...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

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

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

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