二進乗算

仕事がら二進法の乗算の機会は多い. 二進だから十進の九々の代りに一々だけが必要だが, 逆に足す数が多い. 11111(被乗数)に111(乗数)を掛ける例を下の左に示す. 被乗数を乗数に1がある場所に書き移し(今はすべての場所)て部分積を積み重ね, 各桁を二進法で縦に足す. 足すというのは1を数えるだけ. その和が奇数なら, その桁は1; 偶数なら0だ. 和を2で割った商が繰上げで, 次の桁は繰上げから1を足し始める.




つまり, 積の1の桁は, 1が1個だから1で, 繰上げは0; 10の桁は, 0に1,2と数え, 和が2だから積は0, 繰上げは1, 100の桁はその1に3を足し, 積は0で繰上げは2. これを繰り返す. 最後の繰上げは高々1だが, 1ならそれを書いて終る.

右のDCBAなどの図は, 部分積がどのビットの積かを示したものだ. 1の桁はA掛けるa; 10の桁はB掛けるaとA掛けるbの和; 100の桁はC掛けるaとB掛けるbとA掛けるcの和のように見る.

そこで次の図のように, 被乗数DCBAと, 乗数を逆にabcdと書いたカードを作り, 上下に合わせ, 下のカードを順に左へずらしながら, 重なった部分を見ると, その桁で部分積の足し合わせる位置が分かる.



だから, 例えば3番ではCBAとabcで上下がともに1の場所を数えると和が得られる仕掛けである.

11101掛ける1011を, カード方式でやってみると, このようになる.



tはそのカード位置での, 上下が1の場所の数(十進). sはその桁の積(二進). cはその桁からの繰上げ(十進)である.

一番上はtが1. 従って, (その前のcは0なので,) その1からs=1, c=0となる.

2段目, 3段目も繰上げなしなので, 簡単だ. 4段目で繰上げ1が出た. 従って5段目はt=2と4段目のc=1を足して, 3になり, この段のs=1とc=1となる.

cを一瞬だけ記憶し, tを足し, sを書き出し, cを次へ送る. これで乗算が出来るわけだ. 最後のcが1なら, それを書くのも上と同じである.

実際に計算した積, 100111111と同じものが得られている.



ところで最初の計算のように, 1が何個が並んだもの同士の積は簡単である. 2^p-1掛ける2^q-1で考えると, 1かp個と1がq個並んだものを書けるので, (2^p-1)(2^q-1)=2^p+q-2^p-2^q+1.

つまり, p≥qとし, 1の桁を0桁目というと, p+q-1桁目からq桁目まで1を並べ, q-1桁目から1桁目まで0を並べ, 0桁目に1を書き, 最後にp桁目の1を0にする.

p=q=4の場合は, 上の伝で書くと, 1111掛ける1111は11100001だが, これは十六進の九々に相当する, ffe1である. ELIS風ではフフテイだ.