負の値に掛ける正の整数

Question

私はStroustrupの "Principles and Practice Using C++"を読んでC++を学んでいます。事前・事後条件に関するセクションで

機能の次の例があります：

int area(int length, int width) 
// calculate area of a rectangle; 
// pre-conditions: length and width are positive 
// post-condition: returns a positive value that is the area 
{ 
    if (length<=0 || width <=0) 
     error("area() pre-condition"); 

    int a = length*width; 

    if (a<=0) 
     error("area() post-condition"); 

    return a; 
} 

私を混同何このコードについて作業されています

は、値のペアを探しますこのバージョンの前提条件は ですが、後条件はありません。

前提条件はOKですが条件成立していない整数には、可能な値はありますか？

Answer 1

事前条件は成立しているが後条件ではない整数の可能な値はありますか？

はいポスト条件が失敗する可能性のある入力値がいくつかあります。たとえば

int a = length*width; 

正int範囲（std::numeric_limits<int>::max()）をオーバーフローおよびコンパイラの実装は、この場合の負の値をもたらします。

---

他の人がその答えで述べたように、length*widthは]0-std::numeric_limits<int>::max()[からの境界の外に出るような状況は、実際には未定義の動作で、任意の値がaに対して期待することが必要になる場合がありますので、事後条件は、単に役に立たないレンダリングします。

これを解決するための重要なポイントは、@Deduplicatorのanswerに記載されていますが、事前条件を改善する必要があります。

私は彼がそのような未定義の動作がために事後条件で予期せぬ負の値と意外な結果につながる可能性があることを指摘したかったと仮定します。その例を与えるためにビャーネ・ストロヴストルップの推論のためのランスとして

---

素朴な仮定は事前条件でチェックされています。

Answer 2

私の頭に浮かぶのは、署名されたオーバーフローです。これは未定義の動作ですが、負の値を生成する可能性があります。
std::numeric_limits<int>::max()と2を試してください。

Answer 3

いいえ、標準C++の定義された動作の範囲内で、後条件に違反する値はありません。しかし、依然として関数が誤って動作するような値、つまり、その値が非常に大きく、その積が整数に収まらない値があります。 200'000と15'000を渡してみてください。

ほとんどのコンパイラがC++を実装する方法のため、条件違反が発生することがありますが、実際に観察しているのは整数のオーバーフローによる未定義の動作です。

Answer 4

はいあなたはそれが-veの値になるので、そう

{ 
    length = 500, width = 100; 
    if (length<=0 || width <=0) error("area() pre-condition"); 
    int a = length*width; // a = 500 * 100 = 50000 
    if (a<=0) error("area() post-condition"); 
    return a; 
} 

次に、今、最終的な値はa = -17233になりますint型= 2Bの最大値+32767ように、16ビットコンピュータを使用していると仮定した場合。 したがって、2番目の条件はfalseになります。

すべては範囲によって異なります。

Answer 5

INT_MAXは、準拠しているすべてのコンパイラで長さと幅の両方に使用すると、後条件を満たしません。

一つは、INT_MAX> = 32767、そしてINT_MAX*INT_MAXは常にINT_MAXのmaximunの値を保持することができることと定義されてintでINT_MAXよりも大きいため、表現できないだろうというの標準保証するので、それを言うように誘惑されるかもしれません。
これは良い議論であり、実際には最も頻繁に起こることです。ほとんどのコンパイラでオーバーフローが発生します。

しかし、我々は認識しておく必要があり、すべての拠点をカバーすることC++ standard状態：移植性や、誤ったプログラム構築物の使用時に

3.4.3
1未定義の動作
行動、または誤ったデータの場合、この規格は要求を課さない。

2可能性のある未定義の動作は、状況を無視して（診断メッセージの発行の有無にかかわらず）環境の特徴を文書化した方法で翻訳またはプログラム実行中に動作すること、（翻訳メッセージを発行して）翻訳または実行を終了することなどが含まれる。

3例定義されていない動作の例は、整数オーバーフローの動作です。

これは、領域に適切な値が得られないほど深刻です。 INT_MAXを長さと幅の両方（または表現できない結果を含む他の組み合わせ）に使用すると、コンパイルされたプログラムが何を行うかの保証はありません。何でも起れる;オーバーフローやクラッシュのような可能性の高いものから、ディスクフォーマットのような可能性の低いものまで。

Answer 6

答えは彼の前提条件チェックが不完全であることです。あまりにも厳しいですが。
彼は、製品ではなく、UBをもたらすで表すことができることを確認してくださいを含むように失敗しました：オーバーフロービットの数がより多くなり得るので

int area(int length, int width) { 
    // calculate area of a rectangle 
    assert(length >= 0 && width >= 0 && (!width 
     || std::numeric_limits<int>::max()/width >= length)); 
    int a = length * width; 
    assert(a >= 0); // Not strictly neccessary - the math is easy enough 
    return a; 
} 

Answer 7

値型のビット表現をオーバーフロー値の乗算が未定義これにより、正または負の符号ビットで終わる可能性があり、損失ビットの数は可変です。

例1：INT_MAX * 2：結果は正しいですが、上位ビットが符号ビットを表すため、その型で表されていません。

例2：INT_MAX * 4：1ビットがオーバーフローするまで失われ、符号ビットは前の例のように正しくありません。

例3：(INT_MAX + 1) * 2 = 0：すべての設定ビットがオーバーフローしていますが、符号が正しいためです。

私は8ビットのバイナリ表現を使用して読みやすくしています。

0111 1111    // Max positive signed value 
+1 
1000 0000    // Sign bit set but binary value is correct 
*2 
0000 0000    // Upper bit is lost due to overflow 

この場合、ソフトオーバーフローと情報の損失はありませんが、表現が正しくありません。ビットが結果に存在しなくなったところでハードオーバーフローします。

オーバーフローの違いは、オーバーフローを検出する方法です。通常、ハードオーバーフローはハードウェアによって検出され、ソフトウェアが処理する作業はほとんど必要ありません。しかし、ソフトウェアのオーバーフローは、ハードウェアが通常整数演算の符号ビットを認識しないため、ソフトウェアがオーバーフロー状態を明示的にテストする必要があります。

ランタイムライブラリがオーバーフローを処理する方法は、ライブラリに依存します。ほとんどの人がエラーを投げかけるかもしれないが、そうする方が速いのでほとんどの人が無視するだろう。 未定義の動作であっても、ディスクをフォーマットすることはできません。算術演算の結果は、コードのロジックが指示する場合を除いて、コードの流れを変更しません。オーバーフローを無視するか、何らかの方法で処理しようとします。コードまたはハードウェアが問題を処理しようとする場合、標準ではどのメソッドを採用するかは決まっていません。

基本的に3つの可能性があります。
1.オーバーフローは無視され、戻り値は無効です。
2.オーバーフローは実行時ライブラリによって無視されますが、ハードウェアは無視されるエラーをスローし、実行中のコードにハード障害が発生します。この状況では、次に何が起こるかを判断することはOSに完全に依存しています。ナッツを壊してデータを破壊すると、設計上の決定が悪くなります。
3.オーバーフローは実行時ライブラリによって処理されます。これは、処理を進める上で最良の方法を決定する必要があります。通常、これは、コードにエラーをキャッチして処理する機会を与えること、または可能な限り優雅なコードをシャットダウンすることを意味します。

Answer 8

C++ 11テストをすることができるブール値があるので、この値はtrue次いで、署名された算術場合

std::numeric_limits<int>::is_modulo 

は、ラップアラウンド様式で動作し、元のコードには、未定義の動作がありません。負の値が実際に生成される可能性があるため、元のコードのテストは意味があります。乗算でis_modulosee here

Answer 9

だから、基本的には、正の値の更なる議論については

...正の値になるが、これらは実際に結果の型に合わないかもしれません。

前提条件が完全ではなく、事後条件も無効です。負の値だけでなく、入力値よりも小さい正の値を得ることができるだけでなく、ラップアラウンドが0を超えて十分に大きな値、つまりの長尺ラップアラウンドが必要です。

あなたはthisを使用することができます。

bool multiplication_is_safe(uint32_t a, uint32_t b) { 
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b); 
    return (a_bits+b_bits<=32); 
} 

オーバーフローを防ぐために、しかし、その後、あなたは偽陽性の追加検査を採用したいと思います。

パフォーマンスがそれほど問題でない場合は、MPZライブラリを使用できます。パフォーマンスが問題で、オーバーフローフラグが設定されているCPU用のアセンブリを作成する場合は、そのようにすることができます。あなたのコンパイラもあなたのためのチェックを行うことが可能です。 G ++にはfno-strict-overflowがあります。または、前提条件チェック後にunsigned intにキャストしてください。

いずれにせよ、これらのソリューションのほとんどは実際に結果がfooになるという実際の問題を解決するものではありません。つまり、実際の結果よりも小さな領域が得られる可能性があります。

あなたの唯一の安全な選択は、ここに示すように安全な乗算を許可することです。