除算

除算（division）は乗算の逆演算なので， 被除数（dividend）2word，除数（divisor）1word，商（quotient）1wordとしてよい。

除算については二つの方法がある。まず，足し戻し法（restoring method）と呼ばれる方法であるが，これは10進表現の通常の除算のような計算である。一般の足し戻し法では，各桁の計算の際，除数が何回引けるかを推定する必要がある。人間の場合には暗算でおよその目途をつけるのであるが，機械ではそうは行かないので，除数を何回か引いていき，引き過ぎたら除数を足して元へ戻すことを行う。 図 6.10左に，足し戻し法を符号なし整数の2進表現に適用させた場合の例を示すが，結果の各桁の値は0または1しかないので，引けるか引けないかの判断だけである。それでも毎回引いてみて，引けなければ戻すというやや面倒な作業が必要となる。

**Figure 6.10:** 符号なし整数の除算（従来の足し戻し法と突き放し法）
$\begin{figure}\centering \begin{displaymath}\hspace{-1em}\begin{array}{rrlrlrrl... ...1] \\ \cline{2-3} &&0011 &(3) \\ \end{array}\end{displaymath} \end{figure}$

これに対し，突き放し法（non-restoring method）と呼ばれる方法がある。この方法は図 6.10右に示すが，各桁で除数を引いていき，結果が負になっても元に戻さないのである。ただし，そこで引き算は中止する。次の桁の計算では，前の桁で引き過ぎてしまったのだから，今度は除数を足していき，結果が正になったところで止める。以下，符号反転するまで，加算または減算を繰り返すのである。

この突き放し法は， 2進表現された数の場合には特に有利に働く。除数を何回か引いたり，加えたりすると言ったが，これが1回，しかも必ず1回の加減算となるからである。このように，減算が失敗したときにも構わず次のビットの計算に移動できる分，計算速度は速くなる。

なお，被除数が極めて大きく，除数が極めて小さいと，商が1wordを越えてしまうことがある。これをチェックするには，除算を始める前に，被除数の上位の1wordと除数の1wordを比較すればよい。除数の方が小さいときには，商は上位に値を持ち，2wordになるので，エラーとすればよい。

**Figure 6.11:** 突き放し法による符号あり整数の除算
$\begin{figure}\centering \begin{displaymath}\hspace{-1em}\begin{array}{rrlrlrrl... ...4}{c}{\mbox{商は$\underline{0111}$}} \end{array}\end{displaymath} \end{figure}$

符号あり整数の場合にも，まったく同様の議論が成立する。突き放し法による除算の一例を図 6.11に示す。若干ルールがわからないかもしれないが，図中，除数が正の場合には，下線付き数字が0であると次の行で除数を減算， 1であると加算としている。除数が負の場合には，逆になる。

結果である商は，除数が正の場合には，被除数以外の下線付き数字を上から順に読んで， 0と1を反転したものが除算結果となっている。除数が負の場合には，そのままを並べたものとなっている。ただし，除算結果が負の場合には1を加える。

**Figure 6.12:** 突き放し法による余りの処理
$\begin{figure}\centering \begin{displaymath}\hspace{-0.5em}\begin{array}{rrlrl}... ... &&0100 &(4) &\mbox{修正された余り} \end{array}\end{displaymath} \end{figure}$

突き放し法はこのように便利であるが，若干注意が必要である。例えば， $40\div6$ の計算をしてみよう。 図 6.12に示すように，通常の6の倍数の加減算の終了後，余り（remainder）が

2となっている。正の余りとなるはずであるが，符号が逆である。このため，最後に引いた数を戻す必要がある。なお，商はこのままでよい。

本書では，余りの正しい符号は被除数の符号と同じであるとしている。したがって，除算の最後で，被除数が正数で，余りが負数となってしまったときには，除数の絶対値を加え，被除数が負数で，余りが正数となってしまったときには，除数の絶対値を減ずるという補正をする必要がある。

**Figure 6.13:** 除算 $40\div 6=6\cdots 4$ の手順（説明中のMSBは，上位ワードのMSBである。）
$\begin{figure}\centering \begin{displaymath}\hspace{-1em}\begin{array}{rlll} \... ...ne{0110}&\mbox{余りと商} \\ \hline \end{array}\end{displaymath} \end{figure}$

コンピュータ上で除算を行う場合には，乗算と同様，算術演算をなるべく同じところで行いたいので，累計と結果をシフトさせながら，計算を行う。 図 6.13に， 図 6.12に対応するコンピュータ内での除算の手順を示す。 図 6.8に示した乗算の手順と同様に，累計

の右の空き部分に，結果となる

をつめて記載している。見やすくするため，

部分には下線を付した。

また，上位ワード（厳密には下位ワードのMSBを含む）の左シフトの際，溢れを $S_{out}$ として記憶する必要がある。下位ワード（厳密には上位ワードの $\overline{\mbox{MSB}}$ を含む）の際の溢れは無視する。このように，除算でも，必要に応じ，溢れビットを $S_{out}$ として記憶できるような機能を持ったシフタを用意する必要がある。

なお，除数が正の場合には説明にあるように「下位ワードを左シフト（ $\overline{\mbox{MSB}}$ を埋める）」とあるが，除数が負の場合には「下位ワードを左シフト（MSBを埋める）」となることに注意して欲しい。