12

重複の可能性：
C /C++で整数のオーバーフローを検出するための最良の方法

私はインタビューでこの質問をされました：「数の文字列表現を整数に変換する」。ただし、その数が32ビット整数に格納できる最大値を超える場合は、エラーをスローする必要があります。私の質問は、数値が32ビットのunsignedintをオーバーフローするかどうかをどのように確認できるかということです。

4

3 に答える 3

11

ループでは、最初の桁によって決定される整数の現在の値を取得しています。あなたがやろうとしていること:

curval = curval * 10 + digit;  // digit converted from '0'..'9' to 0..9 already

次の方法でオーバーフローをテストできます。

if (curval > UINT32_MAX / 10 || (curval == UINT32_MAX / 10 && digit > UINT32_MAX % 10))
    ...overflow would occur...
else
    curval = curval * 10 + digit; // overflow did not occur

除算と剰余演算はコンパイル時の演算であり、実行時の演算ではありません。

「計算に 32 ビットより大きい符号なし整数」を使用する場合よりもこのアプローチの利点の 1 つはuintmax_t、定数を UINT32_MAX から UINT64_MAX または UINTMAX_MAX に変更することで、より大きな整数 (64 ビット整数と整数)で動作するように拡張できることです。 . 必要なのはこれだけです (もちろん、変数の型を変更する以外は)。

署名された型に対しても同じ基本的なテストが機能しますが、さらに複雑になります。デモ用に 16 ビット整数を使用する方が簡単です (入力して考える桁数が少ない)。そのため、次のように 16 ビットの 2 の補数に切り替えてshortいます。

  • USHRT_MAX= 65535
  • SHRT_MAX= 32767
  • SHRT_MIN= -32768

問題は、short型が -32768 を格納できるが、累積できる最大の正の値が 32767 であることです。SHRT_MIN を除くすべての値について、上記のテストは正常に機能します。このジレンマを回避する方法があります。curval1 つは、計算中に を負の値として格納し、正の値である必要がある場合は返す前に負にすることです。次に、テストは次のようになります。

if (curval < SHRT_MIN / 10 || (curval == SHRT_MIN / 10 && digit > -(SHRT_MIN / 10))
    ...overflow would occur...
else
    curval = curval * 10 - digit; // Note subtraction!

負の値を否定する前に、curvalそうでないことを確認する必要があります。SHRT_MIN(理論的には-SHRT_MAX != SHRT_MIN、2 の補数バイナリ以外のシステムを許可するために、それを確認する必要があります。制限について引用した値はその条件を満たしています。)

もちろん、同じ考え方と手法がINT_MAX、INT32_MAX、INT64_MAXおよびINTMAX_MAXに適用されます。

于 2012-12-01T17:12:58.973 に答える
7

（私はこの質問の重複の可能性を調べましたが、面接の文脈では一般的なアイデア/アプローチを説明することが期待されるため、読むことがどれほど役立つかはわかりません）

面接の質問に答えることの一部は、明確な質問をすることです（面接官があなたに期待する重要なチェックリスト項目の1つ）。

したがって、問い合わせの行には、少なくとも次のようなものを含める必要があります。

  • unsigned long long/ uint64_t（64ビット整数）の使用は許可されていますか？
  • 文字列はどこから来ていますか？stdin/ファイルから読み取る/文字列リテラルとしてハードコードされていますか？
  • それは小数表現としてあなたに与えられますか？2進数/8進数/16進数？
  • どのようなエラーをスローする必要がありますか？回復して実行を継続しようとしていますか？フェイルセーフのデフォルト値は何ですか？

あなたのインタビュアーがそれが小数表現であるとあなたに言うと仮定して+あなたは使うことができますunsigned long long：

  • 最初に桁数を確認します。32ビットのunsigned int範囲は0 to 4,294,967,295。10進数での数値の文字列表現が10文字を超える（10桁を超える）場合、すでにオーバーフローしています。エラーを発生させます。
  • 次に、数値をに保存し、unsigned long longで除算しUINT32_MAX+1=4294967296ます。結果が、より大きい場合0、オーバーフローします。エラーを発生させます。
于 2012-12-01T16:56:19.803 に答える
0

を使用して変換を行いuint64_tます。一度に 1 桁ずつ追加します。数字ごとに 10 を掛けて、次の文字の値を加算します。各文字を処理した後、結果が より大きいかどうかを確認しますUINT32_MAX。そうである場合は、エラーで終了します (または、オーバーフロー時に行うべきことは何でも)。完了したら、数値を として返しますuint32_t。uint64_t、uint32_tおよびUINT32_MAXで定義されていstdint.hます。

于 2012-12-01T17:02:27.583 に答える