乗算

乗算（multiplication）も，基本的には10進表現の乗算とまったく同様であり， 被乗数（multiplicand）を桁をずらして並べ，加算を行うことで，処理する。 図 6.7に，符号なし整数の例を示すが， 加算器が同時に二つの量の加算しかできないことから， 毎行ごとに加算を行うことが，通常の乗算と異なっている。 2進表現におけるメリットとして，乗数（multiplier）の各ビットには0と1しかないため， 0ならば0000（実際には，加算をスキップする）を， 1ならば被乗数そのものを置くだけで，各桁での乗算は不要である。

乗算の結果である積（product）の桁数を考察してみよう。 10進表現の積の場合には，4桁の整数同士の積は最大8桁になる。 2進表現の積の場合でも同様に，4bit同士の積は最大8bitになる。 標準のビット幅をしばしばワード（word）と呼ぶ ^6.7。 したがって，1wordと1wordの積の結果は，最大，2wordになるので， 通常，2word分の領域を確保する。

Figure 6.7: 符号なし整数の乗算

Figure 6.8: 乗算の手順（ $12\times 11=132$）

乗算をコンピュータ内で行う際は，図 6.8のように， 結果の方を，シフタ（shifter）と呼ばれる回路で，右シフトさせながら加算していく。 また，乗数の方も右シフトさせ，シフト溢れ$S_{out}$が0か1かによって， 0のときには何もせず，1のときには乗数を加算する。 このため，結果となる累計$z$の右の空き部分に，乗数$y$をつなぎ， 一緒にシフトしている。 これは，ALUレジスタを無駄に使わないことと， $z$のシフトと$y$のシフトを同時に一つの命令でできることなどである。 見やすくするため，$y$部分には下線を付した。

シフト作業はまず，下位ワード（厳密には上位ワードのLSBも含む）を右シフトし， 溢れたデータを$S_{out}$にセットする。 次に上位ワード（厳密には$C_{out}$を含む）を右シフトする。 このように，必要に応じ，溢れビットを$S_{out}$として記憶できるような機能を持ったシフタを用意する必要がある。

加算は1word用の加算器で無理なく行うことができる。 加算は$S_{out}$=1のときのみ実行され， $S_{out}$=0のときには実行されない。 また，加算の結果，キャリーが生じたときには，$C_{out}$に保存しておく。

同じ原理で，符号あり整数の乗算も可能である。 ただし，正数と正数の積はこれでよいが， いずれかに負数が入っていると，計算は複雑になり，次のような工夫が必要となる。 説明に当たり，負数$-x$の補数表現$16-x$を$\overline x$と記す。 $-y$についても同様である。 また， 積が負数$-xy$になる場合には8bitの補数である$256-xy$を求めることになる。

正数$x\times$正数$y$:

特別な配慮は必要ない。

負数$(-x)\times$正数$y$:

$256-xy=(16-x)y+16(16-y)$なので， 積の8bit補数表現は， $\overline x\,y$に $16\,\overline y$を加える必要がある。

正数$x\times$負数$(-y)$:

$256-xy=x(16-y)+16(16-x)$なので， 積の8bit補数表現は， $x\,\overline y$に $16\,\overline x$を加える必要がある。

負数$(-x)\times$負数$(-y)$:

$xy=(16-x)(16-y)+16(x+y)-256$となるが， 256は8bitの範囲を越えるので無視することにすれば， $\overline x\,\overline y$に 16$x$と16$y$を加える必要がある。

今，元々の4bitの被乗数および乗数を$X$，$Y$で表そう。 もし，$x$が正数であると$X=x$であるし，負数であると$X=16-x$である。 $Y$についても同様とする。 すると，上記の四つの結果は次の1行で表現することができる。

$$XY+\mbox{MSB}(X)\overline Y\times16+\mbox{MSB}(Y)\overline X\times16$$ (6.1)

ここで，MSB$(X)$などは$X$などが正数ならば0，負数ならば1を与える。 コンピュータは，条件により計算手順を変更するのは時間を浪費するため， 嫌われる。 このため，この式のように，条件に依存しない計算手順が好まれる。

このように，乗算の基本的手順は変わらないが， 積の結果である2wordの上位ワードの方に，補正を加える必要がある。 この手法による $(\pm7)\times(\pm6)$の計算を， 図 6.9に示す。 なお，同図右下の $(-7)\times(-6)$の計算で，最終の結果の9bit目に1があるが， これは256であり，8bitの範囲を越えるため，無視することができる。 その結果は期待通り42となる。

Figure 6.9: 符号あり整数同士の乗算

問題7

図 6.9に示した正負4種類の積に対し， 図 6.8のようなコンピュータ内の乗算の手順を示せ。

いずれも積の結果は2wordとしたが，電卓のように扱える最大桁数が決まっていて， 引き続く計算で1wordしか利用できない場合もある。 このような場合には，2wordの結果を出してから，上位ワードに0と1が混載していたら， オーバフローエラーとみなす。 上位ワードが0のみの場合は，1wordで表現できる正数であり， 1のみの場合は，1wordで表現できる負数であり， それ以外の場合は，オーバフローとなるからである。

問題8

二つの符号なし整数に対応して2次元座標系を組み， 横軸，縦軸とも0から15とする。 この座標系で縦軸と横軸の乗算を手計算で行ってみて，結果が1wordを越える領域， 越えない領域を区別してみよ。

問題9

二つの符号あり整数に対応して2次元座標系を組み， 横軸，縦軸とも$-$8から7とする。 この座標系で縦軸と横軸の乗算を手計算で行ってみて，結果が1wordを越える領域， 越えない領域を区別してみよ。