ブースの乗算アルゴリズム
ブースのアルゴリズムは、符号付きの2の補数表現のNビットの乗数 Y において、最下位ビットよりさらに下に y-1 = 0 というビットを暗黙のうちに補って隣接する2つのビットを調べる。Yの各ビット yi(i は 0 から N-1)について、yi と yi-1 を調べる。それら2ビットが同じ場合、積(アキュムレータ) P は変化しない。yi = 0 かつ yi-1 = 1 の場合、被乗数に 2 をかけたものを P に加算する。yi = 1 かつ yi-1 = 0 の場合、被乗数に 2 をかけたものを P から減算する。このようにして得られた P の最終的な値が符号付きの積となっている。
被乗数と積の表現は特に指定されていない。一般にそれらも乗数と同様に2の補数表現とするが、加減算が可能な任意の数値表現が可能である。また、乗数をどちらから調べるかも規定されていない。通常はLSBからMSBへと進め、i = 0 からスタートする。この場合 2 をかける演算は P をステップごとに1ビットずつシフトする操作に置き換え可能となる。シフトではみ出たビットは捨てられ、その後の加減算はPの上位Nビットについてのみ行う。実際には様々な派生や最適化が存在する。