2013-11-22 79 views
1

我在leetcode中編寫了一個簡單問題的代碼。它要求實施pow(x,n);它告訴我「運行時錯誤」,上次執行輸入:1.00000,-2147483648。我改變了另一種方法,這是有效的。但我只是想知道我在做下面的代碼中的錯誤。非常感謝!!我的電源功能實現有什麼問題?

class Solution { 
public: 
    double pow(double x, int n) { 
     // IMPORTANT: Please reset any member data you declared, as 
     // the same Solution instance will be reused for each test case. 
     if(n==0 && x==0) return 1.0; 
     if(x==0) return 0; 
     if(n==0) return 1.0; 
     if(n<0) return 1/pow(x,-n); 
     if(n==1) return x; 

     double y=pow(x,n/2); 
     if(n%2==1) return y*y*x; 
     else return y*y; 

} 

};

+0

當該數字(' - ( - 2147483648)')不能用該數據類型表示時,您正在詢問'-n'作爲整數。結果是未定義的行爲。在函數開始時測試'n'的大小。 – Floris

回答

6

假設int的長度是32位,-2147483648是一個唯一值,不是0,其中它的否定等於它自己。所以行:

if(n<0) return 1/pow(x,-n); 

使用相同的參數調用自己,並這樣做,直到有堆棧溢出。

更詳細地,的-2147483648二進制表示爲:接着31個0小號

10000000000000000000000000000000 

1。根據two's complement採取否定是一個兩步過程。 1)將所有0 s到1,反之亦然:

01111111111111111111111111111111 

然後2)添加1:

10000000000000000000000000000000 

所以我們得到相同的值。因此無限遞歸。

如果您必須處理這種情況,這裏有一個想法。只是n<0測試之前插入此:

if (n==-2147483648) return 1/(x*pow(x,2147483647)); 

顯然,這是此一例黑客攻擊。最終,您的問題域將決定最優雅/一般的解決方案。

+0

表達式-n在這裏實際上有未定義的行爲。但是堆棧溢出是一種常見的觀察行爲,是的。 – aschepler

+0

非常感謝您的回覆。我將它改爲1/pow(x,abs(n));但它仍然不起作用。有任何想法嗎? – user2994219

+1

'abs'不會讓你的編譯器更有能力把'1LL << 32'放入'int'中。你可以做一個特殊的案例測試。 – aschepler

2

-2147483648是十六進制80000000是最大的負數,並且比最大的正數多一個。所以當n = -2147483648時,沒有-n。代碼將失敗

if(n<0) return 1/pow(x,-n); 

這當然是一個特例。

+0

*可能*失敗。不要指望關於未定義行爲的投訴。 – aschepler

+0

鑑於我們被告知代碼失敗,我認爲我們不需要如此謹慎。我們可以假裝成爲程序員一次。 –

+0

我看到足夠的關於「爲什麼沒有這個不安全的代碼失敗/崩潰/錯誤」的stackoverflow問題對於使用任何指示性問題感到緊張。 – aschepler