問題タブ [integer-overflow]

バックグラウンド：

n次のようなボールが与えられた場合:

（もちろんa + b + c + ... = n）

これらのボールを配置できる順列の数は、次の式で与えられます。

perm質問 1:整数オーバーフローをできるだけ長く回避するために「エレガントに」計算するにはどうすればよいですか?また、計算が完了したら、 の正しい値を持っているかperm、最終結果がオーバーフローすることがわかっていることを確認してください。 ?

基本的に、GNU GMP などの使用は避けたいと考えています。

オプションで、質問 2: これは本当に悪い考えですか?

Nを持つ方程式をどのように解くことができますか？その中の定数、ここでNは1 <= N <= 10 ^ 6の範囲である可能性がありますBigIntegerは最大128ビットしか実行できませんか？

両側で対数を実行しても、BigIntegerより大きい値が残ります。

マイクロチップ18f4620PICでの作業。ただし、これは標準のANSICの質問です。

私が持っていると言う

これのバイナリ値は1111 1111 1111 1111です。

もし私が

ビットパターンは1 0000 0000 0000 0000 17ビットになります。明らかにbadFlow == 0、しかし追加の反転ビットはどちらか

1. 破棄されます
2. またはどこにでも存在しますbyte* flowPtr = &badFlow+2; 。

私は後者を想定していますが、前者を望んでいます。

私の問題：同僚が、製造されたすべての製品で約2年間オーバーフローしているカウンターを使用して、いくつかの悪いコードを作成しました。これらのツールの使用に対してお客様が請求する金額を考慮すると、データが不良である可能性があるため、数百万ドルの危険があります。

悲惨な整数オーバーフローが実際にどの程度なのか疑問に思っていました。次のプログラム例を見てください。

a * a32 ビット プラットフォームではオーバーフローが発生し、整数オーバーフローは未定義の動作を引き起こすため、画面に実際に表示されるという保証はありますhello worldか?

次の標準的な引用に基づいて、質問から「署名済み」の部分を削除しました。

(§5/5 C++03、§5/4 C++11) 式の評価中に、結果が数学的に定義されていないか、その型の表現可能な値の範囲内にない場合、動作は未定義です。

(§3.9.1/4) 宣言された符号なし整数は、unsigned2^n を法とする算術法則に従うものとします。ここで、n は、整数の特定のサイズの値表現のビット数です。これは、結果の符号なし整数型で表現できない結果が、結果の符号なし整数型で表現できる最大値よりも 1 大きい数値を法として減らされるため、符号なし算術演算がオーバーフローしないことを意味します。

unsigned intオーバーフローすると何が含まれますか？具体的には、2つunsigned intのsで乗算を行いたいのですunsigned intが、乗算が終了した後はどうなりますか？

最近、一部の古いコードで奇妙な動作が発見されました。このコードは長い間機能していましたが、コンパイラの最適化が最大になっている一部のプラットフォーム (XBox 360、PowerPC) で壊れました。通常、未定義の動作が疑われます。

コードはおおよそ次のようになります。

これはエミュレーターの一部であるため、問題の操作はそれほど奇妙ではありません。通常、これは下位 16 ビットのみを考慮し、それを 32 ビットに符号拡張することを期待します。どうやら、これは長年にわたって行われていた動作でした。x86_64 では、GCC から次の結果が得られます。

ただし、標準について理解できることから、符号なしの値を符号付き型で表すことができない場合、符号なしを符号付きに変換することは定義されていません。

[0, 32767]他の値は未定義であるため、コンパイラは、符号なしの値が の範囲内にある必要があると想定できますか? その場合、へのキャストint16_tとさらに別のキャストへのキャストint32_tは何もしません。この場合、コンパイラがコードを単純な動きに変換することは合法でしょうか?

Cの「標準」符号付き整数型（short、int、longなど）に対するすべての操作は、[TYPE_MIN、TYPE_MAX]間隔（TYPE_MIN、TYPE_MAXが最小および最大整数値）外の結果を生成する場合、未定義の動作を示します。それぞれ、特定の整数型で格納できます。

ただし、C99標準によれば、すべてのintN_tタイプは2の補数表現を持つ必要があります。

7.8.11.1正確な幅
の整数型1.typedef名intN_tは、幅N、パディングビットなし、2の補数表現の符号付き整数型を指定します。したがって、int8_tは、正確に8ビットの幅を持つ符号付き整数型を示します。

intN_tこれは、整数のオーバーフローの場合にC99の型が明確に定義された動作を示すことを意味しますか？たとえば、このコードは明確に定義されていますか？

キャッチがあります！

IEEE 754単精度 (32 ビット) 浮動小数点数が 2 つの連続する 16 ビット整数に格納されています。

私が使用しているプロセッサには、浮動小数点演算や float データ型がありません! 私がやりたいことは、浮動小数点値を 16 ビットの符号付き整数に変換することです。プロセッサには、標準の整数演算とビット操作 (マスキング、シフトなど) があります。

ただし、32 ビットの浮動小数点から 16 ビットの整数に変換する際に、精度をいくらか下げる必要があります。整数には、問題の値の範囲に基づいた暗黙の倍率も必要です。

わかりやすくするための簡単な例を次に示します。float の範囲が0.00～であるとし10.00ます。この場合、整数の範囲を0 to 1000. 100 の暗黙のスケーリング係数に注意してください。この場合、整数の暗黙のスケーリングは 100 です。

IEEE 754には 1 つの符号ビット、指数用の 8 ビット (127 バイアス)、および仮数用の 23 ビットが含まれていることを知っています。

フロートの構成部分から値を再構築する式は次のとおりです。

float 値 = (-1)^Sign_bit * (1+仮数) * 2^(指数-127)。

私が見ることができる主な問題は、16 ビットの符号付き整数 (-32768 から +32767 の範囲) を操作し、オーバーフローまたはアンダーフローを回避することです。

System.out.println(Integer.MAX_VALUE + 1 == Integer.MIN_VALUE);

本当です。

Javaの整数は32ビットであり、2 ³¹ -1を超えることはできないことは理解していますが、ある種の例外ではなく、MAX_VALUE結果に1を追加する理由を理解できません。MIN_VALUERubyのように、より大きなタイプへの透過的な変換のようなものについては言及していません。

この動作はどこかで指定されていますか？頼りにできますか？

私はテッセラル算術でいくつかの作業を行っており、単語の特定の領域でキャリーを検出する必要があります。プログラムの性質上、ビットの位置は入力によって異なります。たとえば、32 ビットのワード サイズで 6 ビットの入力の場合、ビット 19 と 3 の加算キャリーとビット 31 と 15 の減算をチェックすることに関心があります (より一般的には、対象となるビットは (ワード サイズ- 1)、(ワード サイズ / 2 + 入力ビット / 2)、(ワード サイズ / 2 - 1) および (入力ビット / 2))。

私が考えているのは、次のようなものです。

これに対するより良いアプローチはありますか？