3 つの n ビット符号付き整数a、b、およびc(32 ビットなど) の場合、a * (b + c) == (a * b) + (a * c)整数オーバーフローを考慮して、 は常に真ですか?
これは言語に依存しないと思いますが、そうでない場合は、Java の回答に特に興味があります。
1138 次
5 に答える
13
はい、それは成り立ちます。整数演算は有限環上のモジュロ演算だからです。
ここでいくつかの理論的な議論を見ることができます：https ：//math.stackexchange.com/questions/27336/associativity-commutativity-and-distributivity-of-modulo-arithmetic
于 2013-01-07T03:19:46.857 に答える
6
はい、これは常に当てはまります。
これは、2^32を法として効果的に算術演算を行っているために成立するプロパティです。Javaintが署名されているという事実は、物事を少し複雑にします（つまり、一般にモジュロ演算と同等のことをしているとは想定できないことを意味します）が、この特定の分配法則には影響しません。
思考実験は、繰り返し加算を使用して実装することを検討し、オーバーフローしたときに何が起こるかを検討することです。加算を行う順序は（オーバーフローがあっても）sの結果に影響を与えないintため、異なる順序で繰り返される加算として乗算を行うこともありません。また、int乗算は常に繰り返し加算と同等であるため、並べ替えられた乗算の結果も同じである必要があります。QED
于 2013-01-07T03:18:30.157 に答える
2
分配の性質はモジュロ算術にも当てはまります。固定ビット長の 2 の補数の整数演算は、同じ (符号なし) ビット長のモジュロ演算に準同型であるため、2 の補数演算を使用すると、分配特性が保持されます。
詳細については、こちらを参照してください。
于 2013-01-07T03:20:29.087 に答える
1
はい、オーバーフローの場合も含めて、Javaでも当てはまります。（他の特定の言語ではオーバーフロー動作が指定されていません。その場合、保証は行われません。）
于 2013-01-07T03:19:24.687 に答える
0
符号付き整数の 2 の補数計算の場合、質問は次のように要約されます。
is (a*(b+c))%(2**32) === (a*b+a*c)%(2**32)
したがって、2 の補数の符号付き整数演算では常に true です。
2 以外の補数の符号付き整数演算については、オーバーフローの処理方法に依存すると思います。モジュロ演算を反映している場合、それは true です。
于 2013-01-07T03:21:22.767 に答える