ブースの乗算アルゴリズム（ブースのじょうざんアルゴリズム）は、2の補数表現のふたつの符号付整数の乗算の手法である。このアルゴリズムは1950年ごろがロンドン大学バークベック・カレッジで結晶学を研究しているときに発明したものである。ブースは卓上計算機を使って研究していて、計算速度を向上させるために乗算を高速化する方法を探していてこれを発明した。彼の時代のマシンではシフトは加算よりも高速であり、ある種の数値では彼のアルゴリズムは高速であった。しかも負数についてもこのアルゴリズムは機能した。ブースのアルゴリズムはコンピュータ・アーキテクチャの研究において興味深い。ブースのアルゴリズムは、符号付きの2の補数表現の"N"ビットの乗数 "Y" において、最下位ビットよりさらに下に "y" = 0 というビットを暗黙のうちに補って隣接する2つのビットを調べる。"Y"の各ビット "y"（"i" は 0 から "N"-1）について、"y" と "y" を調べる。それら2ビットが同じ場合、積（アキュムレータ） "P" は変化しない。"y" = 0 かつ "y" = 1 の場合、被乗数に 2 をかけたものを "P" に加算する。"y" = 1 かつ "y" = 0 の場合、被乗数に 2 をかけたものを "P" から減算する。このようにして得られた "P" の最終的な値が符号付きの積となっている。被乗数と積の表現は特に指定されていない。一般にそれらも乗数と同様に2の補数表現とするが、加減算が可能な任意の数値表現が可能である。また、乗数をどちらから調べるかも規定されていない。通常はLSBからMSBへと進め、"i" = 0 からスタートする。この場合 2 をかける演算は "P" をステップごとに1ビットずつシフトする操作に置き換え可能となる。シフトではみ出たビットは捨てられ、その後の加減算は"P"の上位"N"ビットについてのみ行う。実際には様々な派生や最適化が存在する。ブースのアルゴリズムは、2つの事前に決定された値 "A" および "S" のうちの1つを積 "P" に繰り返し加算（通常の符号なし2進数の加算）し、"P" を右方向に算術シフトするという形で実装できる。ここで、m を被乗数、r を乗数とし、m のビット数を "x"、rのビット数を "y" とする。3 × -4 を実行する。m = 3、r = −4、"x" = 4、"y" = 4 である。2の補数表現では、表現可能な最小の負数の2の補数を計算すると本来のビット数では表現できない。例えば、被乗数が4ビットなら -8 (1000) という値の2の補数は 8 (01000) となる。つまり A と S で必要とするビット数が異なることになり、上述の実装ではうまく計算できない。1つの解決策として、A、S、P のビット数を1ビット増やせばよい。以下は被乗数も乗数も4ビットのとき −8 × 2 を計算する例である。1の前後を 0で囲んだ正の乗数を考える。例えば、00111110 である。積は以下のようになる。ここで M は被乗数である。演算回数は以下のように書き換えることで 2回にまで減らすことができる。積は被乗数の 1回の加算と 1回の減算で生成される。この手法を 1 のかたまり毎に実施することでいかなる乗数にも適用できる（1が 1ビットしかなくてもである）。したがって以下のようになる。ブースのアルゴリズムはこの手法に従って、1のかたまりの最初に当たったら（0 1）加算を実行し、1のかたまりの最後に当たったら（1 0）減算を実行するものである。この手法は負数の乗算でもうまく機能する。乗数の中の 1 が連続していれば、ブースのアルゴリズムでは一般的な乗算アルゴリズムよりも加算や減算が少なくて済む。逆に 1 が2つ以上連続していない場合、一般的なアルゴリズムよりも加算や減算の回数が多くなってしまう。

出典:wikipedia