2つの数値を掛けて、オーバーフローがあったかどうかを検出したいと思います。それを行う最も簡単な方法は何ですか？
18847 次
6 に答える
12
2 つの 32 ビット数を掛けると 64 ビットの答えになり、2 つの 8 は 16 になります。したがって、2 つの 32 ビット オペランドとビット 17 をオペランド A に設定し、15 または 16 を超えるビットをオペランド b に設定すると、32 ビットの結果がオーバーフローします。左にシフトされたビット 17 16 は、32 に追加されたビット 33 です。
したがって、質問は入力のサイズと結果のサイズです。結果が同じサイズの場合、両方のオペランドの最上位の 1 つを見つけて、結果が結果よりも大きい場合はそれらのビット位置を追加する必要があります。あなたがオーバーフローするスペース。
編集
はい、加算にキャリーがある場合、2 つの 3 ビット数を乗算すると、5 ビット数または 6 ビット数のいずれかになります。同様に、2ビットと5ビットは6ビットまたは7ビットなどになる可能性があります。この質問の投稿者の質問の理由が、結果変数に回答用のスペースがあるかどうかを確認することである場合、このソリューションは機能し、ほとんどの場合比較的高速ですほとんどのプロセッサの言語。あるものではかなり速くなり、他のものではかなり遅くなる可能性があります。オペランドのビット数を見るだけで、一般的に高速です (もちろん実装方法によって異なります)。最大オペランドのサイズを 2 倍にすることは、言語またはプロセッサ内で実行できる場合は安全な方法です。除算は非常に高価 (遅い) であり、ほとんどのプロセッサでは、オペランド サイズを任意に 2 倍にすると、除算がはるかに少なくなります。もちろん、最も速いのは、アセンブラにドロップして乗算を行い、オーバーフロー ビットを確認する (または結果レジスタの 1 つをゼロと比較する) ことです。プロセッサがハードウェアで乗算を実行できない場合、何をしても遅くなります。asm は、はるかに高速で、最も正確なオーバーフロー ステータスを持っているにもかかわらず、この投稿に対する正しい答えではないと推測しています。
バイナリは、10 進数と比較して乗算を簡単にします。たとえば、2 進数を取ります。
0b100 * 0b100
学校での 10 進数の数学と同じように、下位オペランドの最下位ビットから始めて、上位オペランドのすべての位置に対して乗算することができます。ただし、2 進数では、0 を乗算する選択肢は 2 つしかないため、加算する必要はありません。結果に、または 1 を掛けます。つまり、シフトして足すだけです。10 進数の場合のように、実際の掛け算は必要ありません。
000 : 0 * 100 000 : 0 * 100 100 : 1 * 100
列を合計すると、答えは 0b10000 になります
10 進数の 100 列の 1 は、一番上の数字をコピーして 2 つのゼロを追加することを意味します。他の基数でも同じように機能します。したがって、0b100 かける 0b110 は 0b1000 で、2 番目の列に 1 があるので、コピーしてゼロ + 0b10000 を追加し、3 番目の列に 1 を追加します。したがって、2 つのゼロをコピーして追加します = 0b11000.
これにより、両方の数値の最上位ビットが表示されます。0b1xx * 0b1xx は、1xxxx が回答に追加されることを保証します。これは、追加の最大のビット位置であり、最終的な追加への他の単一の入力には、その列またはより重要な列が入力されていません。そこからは、加算される他のビットがキャリーを引き起こす場合に備えて、さらにビットが必要です。
これは最悪の場合、すべての 1 にすべての 1 を掛けた 0b111 * 0b111 で発生します。
0b00111 + 0b01110 + 0b11100
これにより、加算でキャリー ビットが発生し、結果は 0b110001 になります。6 ビット。3 ビットのオペランドに 3 ビットのオペランドを掛ける 3+3=6 6 ビットの最悪の場合。
そのため、最上位ビットを使用するオペランドのサイズ (値を保持するレジスタのサイズではありません) によって、最悪の場合のストレージ要件が決まります。
まあ、正のオペランドを仮定すると、それは真実です。これらの数値の一部が負であると考えると、状況は変わりますが、それほど大きくはありません。
マイナス 4 かける 5、0b1111...111100 * 0b0000....000101 = -20 または 0b1111..11101100
マイナス 4 を表すには 4 ビット、プラス 5 を表すには 4 ビットが必要です (符号ビットを忘れないでください)。すべての符号ビットを取り除いた場合、結果には 6 ビットが必要でした。
4 ビットのコーナー ケースを見てみましょう
-8 * 7 = -56 0b1000 * 0b0111 = 0b1001000 -1 * 7 = -7 = 0b1001 -8 * -8 = 64 = 0b01000000 -1 * -1 = 2 = 0b010 -1 * -8 = 8 = 0b01000 7 * 7 = 49 = 0b0110001
正の数を最上位の 1 プラス 1 としてカウントし、負の数を最上位の 0 プラス 1 としてカウントするとします。
-8 * 7 は 4+4=実際の 8 ビット 7 -1 * 7 は 1+4=5 ビット、実際の 4 ビット -8 * -8 は 4+4=8 ビット、実際の 8 ビット -1 * -1 は 1+1=2 ビット、実際には 3 ビット -1 * -8 は 1+4=5 ビット、実際の 5 ビット 7 * 7 は 4+4=8 ビット、実際には 7 ビットです。
したがって、このルールは機能しますが、-1 * -1 を除いて、マイナス 1 を 1 ビットと呼んでいることがわかります。プラス 1 はゼロ プラス 1 を見つけるからです。とにかく、これが定義どおりの 4 ビット * 4 ビット マシンである場合、少なくとも 4 ビットの結果が得られると私は主張し、答えを安全に保存するために 4 ビットを超える必要があるかどうかという質問を解釈します。したがって、この規則は、2 の補数の数学に関するその質問に答えるのに役立ちます。
あなたの質問がオーバーフローを正確に判断することであり、速度が二次的なものである場合、システムによっては、乗算するたびに非常に遅くなります。これがあなたの質問である場合、速度の一部を元に戻すには、言語やプロセッサに合わせて少し調整する必要があります。可能であれば、最大のオペランドを 2 倍にし、結果のサイズを超えるゼロ以外のビットをチェックするか、除算と比較を使用します。オペランドのサイズを 2 倍にできない場合は、除算して比較します。除算前にゼロをチェックします。
実際、あなたの質問は、あなたが話しているオーバーフローのサイズを指定していません。古き良き8086 16ビット×16ビットは32ビットの結果（ハードウェア）を提供し、オーバーフローすることはありません。乗算、32 ビット x 32 ビット、32 ビットの結果を持ち、オーバーフローしやすい一部の ARM についてはどうですか。この質問のオペランドのサイズはどれくらいですか? 同じサイズですか、それとも入力サイズの 2 倍ですか? ハードウェアが (オーバーフローなしで) 実行できない乗算を実行してもよろしいですか? コンパイラ ライブラリを作成していて、速度を上げるためにオペランドをハードウェアに供給できるかどうか、またはハードウェア乗算なしで計算を実行する必要があるかどうかを判断しようとしていますか。オペランドをキャストアップすると、これが得られます。コンパイラ ライブラリは、乗算を行う前にオペランドをキャストダウンしようとします。もちろん、コンパイラとそのライブラリに依存します。そして、ハードウェアの乗算またはソフトウェアの乗算を使用するために、ビット トリックによって決定されたカウントが使用されます。
ここでの私の目標は、バイナリ乗算が消化可能な形式でどのように機能するかを示すことでした。これにより、各オペランドの単一ビットの位置を見つけることで、必要な最大ストレージ量を確認できます。各オペランドでそのビットをどれだけ速く見つけることができるかが秘訣です。オペランドごとに1ビットだけでなく、両方のオペランドの有効ビットのすべてが含まれるため、最大ではなく最小ストレージ要件を探していた場合、乗算を実行して最小ストレージを決定する必要があります。最大または最小ストレージを気にしない場合は、乗算を実行して、定義されたオーバーフロー制限を超える非ゼロを探すか、時間またはハードウェアがある場合は除算を使用する必要があります。
タグは、浮動小数点に興味がないことを意味します。浮動小数点はまったく別の獣です。これらの固定小数点ルールを浮動小数点に適用することはできません。機能しません。
于 2010-04-26T14:49:57.497 に答える
3
一方が最大値を他方で割った値より小さいかどうかを確認します。(すべての値は絶対値として取得されます)。
x*(2 n - x)>2 M、つまり (x*2 n - x 2 )>2 M、または x 2 < (x *2 n - 2 M )、オーバーフローした数値を比較する必要があります (x 2はオーバーフローする可能性がありますが、結果はオーバーフローしない可能性があります)。
于 2010-04-26T13:57:49.263 に答える
1
数値が最大の整数データ型からのものでない場合は、それらをキャストして乗算し、数値の元の型の最大値と比較するだけです。たとえば Java では、 two を乗算する場合、結果を にキャストする前に、intそれらをキャストして結果をorlongと比較できます(符号の組み合わせによって異なります) 。Integer.MAX_VALUEInteger.MIN_VALUEint
型がすでに最大である場合は、一方が最大値を他方で割った値よりも小さいかどうかを確認します。ただし、絶対値を取らないでください。代わりに、neg neg、pos pos、および pos negの符号の組み合わせごとに個別の比較ロジックが必要です(neg pos は明らかに pos neg に縮小でき、pos pos は neg*neg に縮小される可能性があります)。安全な除算を許可するために、引数が 0 であるかどうかを最初にテストします。
実際のコードについては、commons-math 2 またはcommons-math 3のMathUtilsクラスのJava ソースを参照してください。を探します。a と b が正の場合は、ArithmeticUtilspublic static long mulAndCheck(long a, long b)
// check for positive overflow with positive a, positive b
if (a <= Long.MAX_VALUE / b) {
ret = a * b;
} else {
throw new ArithmeticException(msg);
}
于 2010-04-26T14:43:04.010 に答える
0
Pavel Shvedのソリューションの代替...
選択した言語がアセンブラーの場合、オーバーフロー フラグを確認できるはずです。そうでない場合は、オーバーフロー フラグが設定されている場合に変数を設定するカスタム アセンブラー ルーチンを作成できます。
これが受け入れられない場合は、両方の値 (絶対値) の最も重要なセット ビットを見つけることができます。合計が整数 (または符号なし) のビット数を超える場合、それらを乗算するとオーバーフローが発生します。
お役に立てれば。
于 2010-04-26T14:02:07.163 に答える