math - 2 つの n ビット数を乗算すると、結果は最大のビット長になります。

Question

2 つの n ビットの 2 進数を乗算する場合に必要となる最大ビット数を調べる式または方法があるかどうか疑問に思っていました。私はこれをたくさん検索しましたが、その答えはどこにも見つかりませんでした。

Answer 1

位置システムのベースは重要ではないことに注意してください。10 進数の乗算で思いついた式は、2 進数の乗算でも機能します。

少し控除を適用して、互いに素な桁数を持つ 2 つの数値を掛けてみましょう: それぞれ 2 桁と 3 桁です。

1. 可能な最小数:

   10 * 100 = 1000 は 4 桁

2. 可能な最大数:

   99 * 999 = 98901 は 5 桁

したがって、n 桁と m 桁の乗算の場合、上限と下限はそれぞれn+mとn+m-1桁であると推測されます。バイナリにも当てはまることを確認しましょう。

1. 10 * 100 = 1000 は 4 桁

2. 11 * 111 = 10101 は 5 桁

したがって、それは 2 進法にも当てはまり、どの基数にも当てはまると期待できます。

Answer 2

x は n 個の 2 進数を持ち、2^(n-1) <= x < 2^n であることを意味します。また、y は m 個の 2 進数を持つと仮定します。つまり、次のことを意味します。

2^(m+n-2)<=x*y<2^(m+n)

したがって、x*y は m+n-1 または m+n 桁を持つことができます。両方のケースが可能な例を簡単に作成できます。

• m+n-1: 2*2 には 3 桁の 2 進数があります (m = n = 2)
• m+n: 7*7=49=(binary)110001 には 6 桁の 2 進数があり、m = n = 3