next up previous contents index
Next: 乗算 Up: データの内部表現とその処理 Previous: 整数の内部表現   Contents   Index

2進表現の加減算

まず,2進表現(binary representation)された符号なし整数の加減算(addition and subtraction)の仕方について学ぼう。 例えば11+3の計算は図 6.4のようになされる。 ここで,いくつかの桁で繰り上げが発生すること, ビットによっては1+1=10にさらに繰り上げを加えて, 10+1=11になることなどに注意して欲しい。

Figure 6.4: 2進表現による符号なし整数の加算(括弧内は10進表現)
\begin{figure}\centering
\begin{displaymath}\begin{array}{rrr}
& 1011 & (11) \...
...011 & (3) \\
\hline
& 1110 & (14)
\end{array}\end{displaymath}
\end{figure}

この計算で若干問題があるのは,極めて大きな数同士を加えると, 元は4bit以内の数であっても,和が16を越えてしまい, 5bitを使わないと表現できなくなってしまうことがあることである。 この5bit目を, 通常のコンピュータでは,加算全体のキャリー出力$C_{out}$として, 計算結果とは別のところへ出力する。 また,こうしたbit幅溢れが起こることをオーバフロー(overflow)と呼ぶ。

問題3
11+7=18の計算でオーバフローが起こることを示せ。
問題4
二つの正整数に対応して2次元座標系を組み,横軸,縦軸とも0から15とする。 この座標系で縦軸と横軸の加算を行った際,オーバフローの起こる領域, 起こらない領域を区別してみよ。 この結果,全計算の約半分がオーバフローを起こすことが理解できよう。

次に符号あり整数の加算を考えよう。 オーバフローのことを無視すれば, 正数と正数の和は符号なし整数の加算とまったく同じである。

負数のある場合の加算を考えよう。 前節で述べたように,負数は補数表現する。 つまり元の負数に16(2進表現では1 0000)を加えた数を用いることにする。 例えば$-$1を表すには,15(2進表現では1111)とする。 こうすると,正数と負数の加算の結果は16だけ大きな値となるが, 図 6.5のように,正しい結果となる。

Figure 6.5: 2進表現による符号あり整数,負数+正数の加算(ビット幅を越える部分は無視する)
\begin{figure}\centering
\begin{displaymath}\begin{array}{rrr}
& 1101 & (-3) \...
...0101 & (5) \\
\hline
& 0010 & (2)
\end{array}\end{displaymath}
\end{figure}

ただし,和の結果が7以上または$-$8以下となるときには,必ずオーバフローとなる。 オーバフローは正数と正数の和,または負数と負数の和の場合だけ発生する。 正数と負数の和は必ずこの範囲に納まる。 正数同士の和の場合,オーバフローが起こるとMSBに1が立つ。 オーバフローは二つの数が負数の場合にも発生する。 このとき,MSBは0となる。 つまりオーバフローは,二つの正数の和でかつ加算結果のMSBが1か, 二つの負数の和でかつ加算結果のMSBが0の場合を検出すればよい。

問題5
符号あり整数として$-$8(1000)に順に1を加えていき, 4bitの範囲のみに着目すると,図 6.3になることを確認せよ。
問題6
二つの符号あり整数に対応して2次元座標系を組み, 横軸,縦軸とも$-$8から7とする。 この座標系で縦軸と横軸の加算を行った際,オーバフローの起こる領域, 起こらない領域を区別してみよ。 この結果,全計算のおよそ1/4がオーバフローを起こすことが理解できよう。 またオーバフローを起こすことを検出するには, 上記の判断法が適切であることも理解できよう。

減算(subtraction)により(difference)を求めるプロセスは容易である。 減数の方を符号反転して加算すればよい。 符号反転とは補数を得ることであるので,すべての0と1をビット反転し, 1を加えればよい。 符号あり整数の場合,$-$8の補数は存在しないので,注意が必要である。 ちなみに,$-$8(1000)をビット反転すると7(0111)であるが, これに1を加えると,8となって範囲外となる。 この際,オーバフローが発生する。

どのような場合に減算の計算結果が4bit幅の範囲で正しく表示されるのか, 4bit幅の範囲で正しく表示されない場合には, 5bit目に繰り上げされたキャリーで,真の値が判断できるはずであるが, どのように判断すればよいのかは, 符号なし整数の減算の場合と符号あり整数の減算の場合で異なるが, これは各人で考えてもらいたい。

符号なし整数では最大値15, 符号あり整数では$-$8から7までの16個の数しか表現できない。 これでは,あまりに小さな数しか計算の対象にできないことになる。 データ幅を大きくしないで,もっと大きな数を扱うには, 元の数を4bitごとに区切って扱えばよい。 例えば4bit数を2組用意すれば,256個の数を扱うことができる。 10進表現の数でも1桁で表現しろと言われれば, 0から9までの10個の数しか表現できないが, 2桁使えば,0から99まで表現できるようになるのと同じ理由である。

Figure 6.6: 2進表現による大きな数の加算
\begin{figure}\centering
\begin{displaymath}\begin{array}{rrrr}
& 0011&1101 & ...
...-26) \\
\hline
& 0010&0011 & (35)
\end{array}\end{displaymath}
\end{figure}

それでは,こうした大きな数の加減算はできるのであろうか。 図 6.6には非加数,加数とも, 8bitの符号あり整数の加算を示す。 まず,下の4bitの加算は符号なし整数の加算を行っており, 上の4bitの加算は符号あり整数の加算を行っている。 さらに下4bitの加算はオーバフローを起こしており, さらに上の桁へのキャリーが発生している。 したがって,上の4bitの加算の際には,この下からのキャリーを加えて行っている。 これだけの手順で,8bitの加算が可能なのである。

二つの大きな整数の加減算の手順を改めて述べると

  1. まず,二つの整数を4bitの整数倍のbit数に揃える。 この際,ともに大きいbit数の整数の方に合わせる。 符号あり整数で負数の場合には,最上位まで1を埋める。
  2. それぞれの4bitごとに下位から順に加算を行う。
  3. 下の4bitの加算全体でキャリーが発生した場合には, 上の4bit加算へ繰り上げる。
  4. 最上位の4bit加算は符号あり整数か符号なし整数かを意識して行う。 それ以外の4bit加算はすべて符号なし整数として行う。
このようにして,いくら大きな加減算でも実行することができるのである。


next up previous contents index
Next: 乗算 Up: データの内部表現とその処理 Previous: 整数の内部表現   Contents   Index
Yoichi OKABE 2008-03-29