[解決済み] ビットシフトと加算だけで乗除する方法は？

質問

ビットシフトと加算だけで乗除算を行うにはどうしたらよいでしょうか？

どのように解決するのですか？

足し算とずらし算の掛け算は、片方の数字を2の累乗で分解して、このようにしたい。

21 * 5 = 10101_2 * 101_2             (Initial step)
       = 10101_2 * (1 * 2^2  +  0 * 2^1  +  1 * 2^0)
       = 10101_2 * 2^2 + 10101_2 * 2^0 
       = 10101_2 << 2 + 10101_2 << 0 (Decomposed)
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5                      (Same as initial expression)

( _2 はベース2を意味する)

見ての通り、乗算は加算とシフトに分解でき、また元に戻ることができます。これは、乗算がビットシフトや加算よりも時間がかかる理由でもあり、ビット数では O(n) ではなく O(n^2) となります。現実のコンピュータシステムは（理論上のコンピュータシステムとは対照的に）有限のビット数を持っているので、乗算は加算やシフトに比べ一定の倍数の時間がかかるのです。私の記憶が正しければ、最近のプロセッサは、適切にパイプライン化されていれば、プロセッサ内の ALU (演算ユニット) の使用率をいじることによって、乗算を加算と同じくらい速く実行することができます。