3

誰かが私のためにこの機能を説明するのに十分親切にしてくれませんか？ありがとう！

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));  
}
4

1 に答える 1

5

これは、加算演算の積分オーバーフロー「フラグ」を計算しています。これは、結果の大きさが。より小さいINT_MINか大きいかを表しINT_MAXます。これは、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 );

編集：おっと、私は関数がオーバーフローフラグで何をしたかを推測しませんでした。明らかに、オーバーフローがない場合は結果を返しINT_MAX、正のオーバーフローがある場合は戻りINT_MIN、負のオーバーフローがある場合は戻ります。言い換えれば、それは飽和した追加です。これを行う方法は少し複雑で、作者は枝を取り除くのに苦労したようです。ただし、通常はオーバーフローは発生せず、予測可能な分岐は多くの演算よりも安価であるため、を使用してより簡単な実装を試す価値がありif … elseます。

于 2013-02-06T23:06:11.187 に答える