91

一見すると、この質問は整数オーバーフローを検出する方法の重複のように思えるかもしれません。ですが、実際には大きく異なります。

符号なし整数のオーバーフローを検出することは非常に簡単ですが、C/C++ で符号付きオーバーフローを検出することは、実際にはほとんどの人が考えるよりも難しいことがわかりました。

それを行うための最も明白でありながら単純な方法は、次のようなものです。

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

これに関する問題は、C 標準によると、符号付き整数のオーバーフローが未定義の動作であることです。 言い換えれば、標準によれば、符号付きオーバーフローを引き起こすとすぐに、プログラムは null ポインターを逆参照した場合と同じように無効になります。したがって、未定義の動作を引き起こすことはできず、上記の事後条件チェックの例のように、事後にオーバーフローを検出しようとします。

上記のチェックは多くのコンパイラで機能する可能性がありますが、期待することはできません。実際、C 標準では符号付き整数のオーバーフローは未定義であると述べられているため、最適化フラグが設定されている場合、一部のコンパイラ (GCC など) は上記のチェックを最適化して除外します。これにより、オーバーフローをチェックする試みが完全に中断されます。

したがって、オーバーフローをチェックする別の方法は次のとおりです。

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

このような加算を実行してもオーバーフローが発生しないことを事前に確認するまで、2 つの整数を実際に加算しないため、これはより有望に思えます。したがって、未定義の動作は発生しません。

ただし、残念ながら、このソリューションは、加算演算が機能するかどうかをテストするためだけに減算演算を実行する必要があるため、最初のソリューションよりも効率が大幅に低下します。この (小さな) パフォーマンス ヒットを気にしないとしても、このソリューションが適切であると完全に確信しているわけではありません。この式lhs <= INT_MIN - rhsは、符号付きオーバーフローが不可能であると考えて、コンパイラが最適化して取り除く可能性のある式とまったく同じように見えます。

ここでより良い解決策はありますか？1) 未定義の動作を引き起こさないこと、および 2) オーバーフロー チェックを最適化する機会をコンパイラに提供しないことが保証されているものはありますか? 両方のオペランドを符号なしにキャストし、独自の 2 の補数演算をローリングしてチェックを実行する方法があるのではないかと考えていましたが、その方法がよくわかりません。

4

13 に答える 13

40

いいえ、2 番目のコードは正しくありませんが、近いです: 設定した場合

int half = INT_MAX/2;
int half1 = half + 1;

加算の結果は ですINT_MAX。(INT_MAXは常に奇数です)。したがって、これは有効な入力です。しかし、あなたのルーチンでは、あなたは持っていてINT_MAX - half == half1、中絶するでしょう. 誤検知。

このエラーは、両方のチェック<の代わりに配置することで修復できます。<=

しかし、あなたのコードも最適ではありません。次のようにします。

int add(int lhs, int rhs)
{
 if (lhs >= 0) {
  if (INT_MAX - lhs < rhs) {
   /* would overflow */
   abort();
  }
 }
 else {
  if (rhs < INT_MIN - lhs) {
   /* would overflow */
   abort();
  }
 }
 return lhs + rhs;
}

これが有効であることを確認するにlhsは、不等式の両側を記号的に追加する必要があります。これにより、結果が範囲外であるという算術条件が正確に得られます。

于 2010-10-16T06:41:18.590 に答える
28

減算によるあなたのアプローチは正しく、明確に定義されています。コンパイラはそれを最適化することはできません。

より大きな整数型を使用できる場合のもう 1 つの正しいアプローチは、より大きな型で演算を実行し、変換を戻すときに結果がより小さな型に収まるかどうかを確認することです。

int sum(int a, int b)
{
    long long c;
    assert(LLONG_MAX>INT_MAX);
    c = (long long)a + b;
    if (c < INT_MIN || c > INT_MAX) abort();
    return c;
}

優れたコンパイラは、加算とifステートメント全体をint-size の加算と単一の条件付き jump-on-overflow に変換し、実際にはより大きな加算を実行しないようにする必要があります。

編集: Stephen が指摘したように、(あまり良くない) コンパイラ gcc で正常な asm を生成するのに問題があります。生成されるコードはそれほど遅くはありませんが、最適ではないことは確かです。gcc が正しいことを行うようにする、このコードの変形を誰かが知っているなら、私はそれらを見たいと思っています。

于 2010-10-15T17:57:06.370 に答える
16

IMHO、オーバーフローセンシティブ C++ コードを処理する最も簡単な方法は、を使用することSafeInt<T>です。これは、コード プレックスでホストされるクロス プラットフォームの C++ テンプレートであり、ここで必要な安全性の保証を提供します。

通常の数値演算と同じ使用パターンが多く、例外を介してオーバーフローとアンダーフローを表現するため、非常に直感的に使用できます。

于 2010-10-15T17:32:48.977 に答える
11

インライン アセンブラを使用する場合は、オーバーフロー フラグを確認できます。もう 1 つの可能性は、 safeint データ型を使用できることです。Integer Securityに関するこの論文を読むことをお勧めします。

于 2010-10-15T17:32:31.473 に答える
1

64 ビット整数に変換して、同様の条件をテストする方がうまくいくかもしれません。例えば：

#include <stdint.h>

...

int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
    // Overflow occurred!
}
else {
    return sum;
}

ここで符号拡張がどのように機能するかを詳しく見てみたいと思うかもしれませんが、それは正しいと思います。

于 2010-10-15T17:31:11.843 に答える
1

明らかな解決策は、unsigned に変換して、明確に定義された unsigned オーバーフロー動作を取得することです。

int add(int lhs, int rhs) 
{ 
   int sum = (unsigned)lhs + (unsigned)rhs; 
   if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { 
      /* an overflow has occurred */ 
      abort(); 
   } 
   return sum;  
}

これにより、未定義の符号付きオーバーフロー動作が、符号付きと符号なしの間の範囲外の値の実装定義の変換に置き換えられるため、何が起こるかを正確に知るためにコンパイラのドキュメントを確認する必要がありますが、少なくとも明確に定義されている必要があります。過去 20 年間に構築されたほぼすべてのマシンと C コンパイラがそうであるように、変換時にシグナルを発生させない 2 の補数のマシンで正しいことを行う必要があります。

于 2010-10-15T22:22:32.860 に答える
1

どうですか：

int sum(int n1, int n2)
{
  int result;
  if (n1 >= 0)
  {
    result = (n1 - INT_MAX)+n2; /* Can't overflow */
    if (result > 0) return INT_MAX; else return (result + INT_MAX);
  }
  else
  {
    result = (n1 - INT_MIN)+n2; /* Can't overflow */
    if (0 > result) return INT_MIN; else return (result + INT_MIN);
  }
}

INT_MINこれは、正当なand INT_MAX(対称的かどうかにかかわらず)に対して機能するはずだと思います。表示されたクリップとして機能しますが、他の動作を取得する方法は明らかなはずです)。

于 2010-10-15T20:47:32.620 に答える
-1

私にとって、最も簡単なチェックは、オペランドと結果の符号をチェックすることです。

合計を調べてみましょう。オーバーフローは、両方のオペランドが同じ符号を持つ場合にのみ、+ または - の両方向で発生する可能性があります。そして、明らかに、結果の符号がオペランドの符号と同じではない場合にオーバーフローが発生します。

したがって、次のようなチェックで十分です。

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

編集：Nilsが示唆したように、これは正しいif条件です：

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

そしていつからその指示

add eax, ebx

未定義の動作につながる？Intel x86命令セットリファレンスにはそのようなものはありません..

于 2010-10-15T20:46:35.897 に答える
-3

これはうまくいくと思います：

int add(int lhs, int rhs) {
   volatile int sum = lhs + rhs;
   if (lhs != (sum - rhs) ) {
       /* overflow */
       //errno = ERANGE;
       abort();
   }
   return sum;
}

volatile を使用するsumと、加算と減算の間で変更された可能性があるとコンパイラが判断するため、コンパイラはテストを最適化できなくなります。

x86_64 用の gcc 4.4.3 を使用すると、このコードのアセンブリは加算、減算、およびテストを実行しますが、スタック上および不要なスタック操作のすべてを格納します。試してみregister volatile int sum =ましたが、組み立ては同じでした。

（揮発性またはレジスタなし）のみのバージョンではint sum =、関数はテストを実行せず、1 つのlea命令のみを使用して加算を実行しました（lea有効アドレスのロードであり、フラグ レジスタに触れずに加算を行うためによく使用されます）。

あなたのバージョンはより大きなコードで、より多くのジャンプがありますが、どちらが優れているかわかりません。

于 2010-10-15T19:39:06.120 に答える