ブースの乗算アルゴリズム
1の前後を 0で囲んだ正の乗数を考える。例えば、00111110 である。積は以下のようになる。
M × ′ ′ 0 0 1 1 1 1 1 0 ′ ′ = M × ( 2 5 + 2 4 + 2 3 + 2 2 + 2 1 ) = M × 62 {\displaystyle M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}
ここで M は被乗数である。演算回数は以下のように書き換えることで 2回にまで減らすことができる。
M × ′ ′ 0 1 0 0 0 0 -1 0 ′ ′ = M × ( 2 6 − 2 1 ) = M × 62 {\displaystyle M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62}
積は被乗数の 1回の加算と 1回の減算で生成される。この手法を 1 のかたまり毎に実施することでいかなる乗数にも適用できる(1が 1ビットしかなくてもである)。したがって以下のようになる。