はじめに
- プログラミング初学者向けに
- 数学における減算が負の数の導入で加算に組み込まれたことを、コンピュータ上でも同様であることを示し
- 符号化の端緒として符号付き整数を学ぶ
負の数 = 2の補数 = 符号付き整数
負の数
コンピュータは0と1しか持っていないので、0と1をどう組み合わせても負になりようがない。したがって、0と1の組み合わせでできる数に負の数の性質を持つものを選んで、それを負の数と見なすことにする。負の数とは、加算すると0になる数のことである。確かに、$(- 1) + 1= 0$である。 まず$-1$を考えてみよう。負の数$-1$はどのような表現が妥当だろうか？
これは8ビットで考えた場合、$11111111$であると都合がよい。コンピュータ上の数は有限桁なので、最上位の繰り上がりは加算の結果に含めないことにできる。ここで、$\equiv$はコンピュータ上では、の意味。
\begin{array}{cr|r|rrr}
& ‐1 & ???????? & & 11111111 & \\
+)& 1 & 00000001 & & 00000001 & \\ \hline
& 0 & 00000000 & 1 & 00000000 & \equiv 0\\
\end{array}
したがって、今、負の数を$x_{-}$とすると、加算すると0になる数という性質は、次の通りになる。
x_- + x = x + x_- = 2^8 \equiv 0
2の補数
さて、ある数$x$に$x_c$を加算してある数$C$になるとき$x_c$は$x$の補数といい、さらに$C$が基数2のべき乗になるとき特に$x_c$を2の補数という1。これを式で表すと、
x + x_c = C = 2^n
である。そこで$n=8$ で考えると、この2の補数$x_c$は、加算すると0になるという負の数の性質を満たすことに気づく。
\begin{cases}
x + x_- =2^8 \\
x + x_c = 2^8
\end{cases}
\quad
\Longrightarrow
\quad
x_- = x_c
したがって、$x$を正の数とし、$x$に対する2の補数$x_c$を負の数$-x$として採用する。
ここで、2の補数$x_c$は論理演算NOTを施して1を加えることで容易に作ることができる。$x$+NOT($x$)は常にすべての桁が1になるため、さらに1を加えることで繰り上がって基数2のべき乗になる。
\begin{array}{rrrrr} \hline
& 1 & 127 & -1 & \\ \hline
x & 00000001 & 01111111 & 11111111 & \\ \hline
NOT(x) & 11111110 & 10000000 & 00000000 & \\ \hline
x + NOT(x) & 11111111 & 11111111 & 11111111 & \\ \hline
x + NOT(x) +1 & 100000000 & 100000000&100000000 & \equiv 0 \\ \hline
\end{array}
つまり、$x+ $ NOT ($x$)$ + 1 = 2^n $が成り立ち、また$x + x_c = 2^n $であるから、 $x_c = $ NOT ($x$)$ + 1$である。
以上により、負の数$-x$ を$-x := x_- = x_c = $ NOT($ x $)$ + 1$ である。$x$が与えられれば$-x$を計算できる。なお、$n=8$で検討したが、これは繰り上がりするビット長で常に成り立つ。
符号付き整数
ところで、-1 = 11111111はこれまでの数の表現であれば255のはずである。これは、コンピュータ上の数には解釈の違いが生じたことを意味する。ここでは、負の数と解釈しうる場合を正負の符号付き整数と、そうでないこれまでの正の数しかない場合を符号なし整数として区別する。
有限桁で表現した数のうち、最上位桁を正負の符号と解釈する整数の表現を、符号付き整数という。
\begin{array}{rrrrrrrrrr}
-2^7 & 2^6 & 2^5 & 2^4 & 2^3 & 2^2 & 2^1 & 2^0 & \\
-128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 & \\ \hline
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & = & 127 \\ \hline
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & = & -128 \\\hline
\end{array}
符号付き整数の表現する最大値と最小値はビット長によって異なる。
| ビット長 | 符号なし整数最小値 | 最大値 | 符号付き整数最小値 | 最大値 |
|---|---|---|---|---|
| 8 | 0 | $255$ | $-128$ | $127$ |
| 16 | 0 | $65535$ | $-32728$ | $32727$ |
| 32 | 0 | $ 2^{32} $ | $- 2^{31}$ | $2^{31} - 1$ |
| n | 0 | $ 2^n $ | $- 2^{n-1}$ | $2^{n-1} - 1$ |
加算器の拡張
補数器と多ビット加算器による加減算器
1ビット加算器の$C_o$を別の1ビット加算器の$C_i$に繋ぎ複数組み合わせると多ビット加算器になる。最下位ビットに相当する1ビット加算器の$C_i$は0とすると、そのまま有限桁の加算ができる。ここで、この最下位ビットの$C_i$が肝となる。
通常の加算の場合は、$C_i = 0$である。
負の数を2の補数として表現すると、減算を加算で計算できる。つまり、$a - b = a + (-b) = a + $ NOT( $b$ )$ + 1$である。加算器への入力として、$b$をNOT($b$)にし、$C_i = 1$にする補数器を接続すれば、減算の場合も加算器をそのまま再利用できる。
補数器の入出力は次表の通り。各桁にXOR演算を施せばよい。減算の時にbがNOT($b$)になるということは、出力はXORになる。
| 入力 | ||||
|---|---|---|---|---|
| $s$ : 加算(=0)/減算(=1) | 0 | 0 | 1 | 1 |
| $b$ | 0 | 1 | 0 | 1 |
| 出力 = $s$ XOR $b$ | 0 | 1 | 1 | 0 |
その他の計算
減算が加算を用いて実現できたように、$b$の加工と$C_i$の組み合わせで、$+1$と$ -1$も実現できる。
| 演算 | $ b $ | $C_i$ | 出力式 |
|---|---|---|---|
| 加算 | $b$ | 0 | $a + b + 0$ |
| 減算 | NOT($b$) | 1 | $a + $ NOT( $b$ )$ + 1$ |
| $+1$ | 0 | 1 | $a + 0 + 1$ |
| $-1$ | -1 | 0 | $a - 1 + 0$ |
発展
次の発展方向がある。
- CPUへ: 比較器->選択器->ビット演算器->算術演算器->ALU->メモリ->カウンタ->クロックジェネレータ->CPU
- デバイス制御へ: 論理回路設計->7/8セグメント->Lチカ->電子工作
まとめ
- 負の数は2の補数であることを示した
- 減算が加算と共通化できることを学んだ
- 符号付き整数として、同じビット列でも解釈が異なることを示した
おわりに
- 本稿では負の数の導入に、負の数の性質と2の補数が類似することを明示した
- 2の補数の導入として減算が加算でできることを説明するが、それは数の範囲を自然数に負の数を加えて整数に拡張するからいえることであって、負の数がなんであるか説明していないことに違和感があった
- そこで、本稿では負の数は「加算すると0」になる数という性質から導いた体裁にした
- また、2の補数で負の数を置き換えて加算することで、繰り上がりの最上位桁を華麗にスルーする説明になっている
- ここも、本稿では「有限桁であるから」と無視してよい理由を明示した
-
基数2のべき乗である数$2^n$は二進法では必ず最上位桁のみが1になる ↩