需要幫助瞭解整數運算功能

會有人請還跟我感謝你解釋一下這個功能！需要幫助瞭解整數運算功能

int overflow(int x, int y) 
{ 
    int result, non_overflow, overflow, result_sign, mask; 

    result = x + y; 
    result_sign = result >> 31; //Need help starting from here... I know 
           //it is shifting 31 bits... but why?? 
    non_overflow = ((x^y) | ~(y^result)) >> 31; 
    overflow = ~non_overflow; 

    mask = overflow << 31; 

    return (non_overflow & result) | (overflow & (result_sign^mask)); 
}

來源

2013-02-06 juice

你有沒有拍過兩對數字（一個是在添加時溢出，一個是沒有的），然後通過手動或者在調試器中通過算法來看*每個操作發生了什麼？ – WhozCraig

沒有想到這一點。謝謝。順便說一句..你怎麼讓它溢出？ – juice

最簡單的方法？ '溢出（MAX_INT，MAX_INT）'應該這樣做。但是，這一切都需要在32位''平臺上運行，否則無論如何這都不起作用。看起來你已經從標籤中知道，但是。 – WhozCraig

它計算所述加法運算，其表示結果的幅度是否比INT_MAX大於小於INT_MIN或一體溢出「標誌」。它假定int爲32位，2的補碼和有符號數的右移是「算術」移位它複製高位 - 沒有安全的假設。

如果x和y的符號相同，但結果符號相反，則結果溢出。這就是計算。沒有必要這麼複雜。

假設除了不產生積分的異常，也沒有靠不住的奇偶校驗位，這個表達式將作爲原始代碼以同樣的精神操縱符號位工作：

(x^y) < 0 && (x^result) < 0 /* (A^B)<0 iff A and B have opposite sign */

如果我們想被挑剔依託良好定義的行爲，執行x + y是非法如果結果可能會溢出。符合C標準的機器被允許以這樣的溢出（或自毀等）終止程序，所以我們首先需要避免這樣做。

我們要執行的測試是

x + y > INT_MAX 
x + y < INT_MIN

有直接x和y之間沒有安全運行。我們必須將一個移到等式的另一邊，這意味着顛倒它的符號並進行減法。這只是安全地從INT_MAX減去一個正數，或者從INT_MIN減去一個負數，所以我們可以修改這些：

y > INT_MAX - x 
y < INT_MIN - x

做最安全的方式是那麼

x < 0? (y < INT_MIN - x) : (y > INT_MAX - x);

編輯：Woops，我沒有猜到該函數用溢出標誌做了什麼。它顯然返回的結果，如果沒有溢出，則返回INT_MAX如果有積極的溢出，並INT_MIN如果有一個負溢出。換句話說，它是飽和的加法。它的做法有點複雜，看起來作者很努力去消除分支。但溢出通常不會發生，而可預測的分支比許多算法便宜，因此使用if … else可能更值得嘗試更直接的實現。

來源

2013-02-06 23:06:11 Potatoswatter

這是如何做到這一點的正確方法了相當全面的破敗：http://www.fefe.de/intof.html – datenwolf

需要幫助瞭解整數運算功能

回答

相關問題