素人が迷い込んだ補数と基数と減基数の世界

0. はじめに

　コンピュータについての本を読んでいたとき、「コンピュータは２の補数を使って負数を表現し、負数の加算によって減算を行う」と書いてあった。コンピュータについて知識が薄い自分からすると、「減算すればいいのでは？補数なんていらないのでは？」といった感じであった。

　これを理解するには、n進法の性質とコンピュータの仕組みについて知る必要があった。今回はそれをまとめる。

1. 語句の確認

1.1 基数とは

　数値の表現方法で、位取りを行う数字のこと。2進数では2、10進数では10、n進数ではnが基数になる。底ともいう。

1.2 補数とは

　Wikipediaによる説明では、

補数（ほすう;complement）とは、ある基数法において、ある自然数 a に足したとき桁が1つ上がる（桁が1つ増える）数のうち最も小さい数をいう。
https://ja.wikipedia.org/wiki/%E8%A3%9C%E6%95%B0

と、ある。

馴染みのある10進法で具体的に見てみよう。

• $4 + 6 = 10$
• $4 + 11 = 11$
• $4 + 96 = 100$

4に6や11や96を足しても桁は増えるが、その最小の数は6なので、10進法においては「4の補数は6」となる。同様に、「１4の補数は86」、「114の補数は886」となる。

• $ 4 + 6 = 10 $
• $ 14 + 86 = 100 $
• $ 144 + 886 = 1000 $

つまり補数とは、ある数の桁をあげるのを「補」ってあげる数だ。

1.3 減基数とは

　またまたWikipediaによる定義では、

b 進法において、自然数 a を表現するのに必要な最小の桁数を n としたとき、
・ $b^{n}-a$ を 「b 進法における a に対する基数の補数（b の補数）」
・ $b^{n}-a-1$ を「b 進法における a に対する減基数の補数（b - 1 の補数）」
という。

とある。「減基数の補数」という表現で使われるらしい（減基数それ自体の言葉の定義を調べたが出てこなかった汗）。

　ここにあるように「減基数の補数」とは、あと１で桁が上がる直前の数だ。補数の定義との兼ね合いで言えば、「足したときに桁が上がらない数のうち最大の数」と言える。10進法において、4の減基数の補数は5、14の減基数の補数は85、１４４の減基数の補数は885、となる。減基数の補数を足すと、$基数-1$(今回は$10 - 1 = 9$)の数が各桁に並ぶことになる。

• $ 4 + 5 = 9 $
• $ 14 + 85 = 99 $
• $ 144 + 885 = 999 $

　減基数の補数とは 、桁が上がるには少し「元気」が足りない数のことだ。

　以上、１０進数の世界における補数等の振る舞いを見てきた。次は２進数の世界における振る舞いを見ていこう。

2. ２進数の世界

　2進数における減基数の補数から求めよう。減基数の補数は桁が上がる直前の数だった。つまり、$11111.....11$のように$1$が連続して並ぶようなものだ。

　$11001$を具体例として考えよう。これの減基数の補数は、$00110$だ。確かに両者を足すと$11111$となる。これの求め方は、$11001$の$1$を$0$に、$0$を$1$にひっくり返してあげればいい。

　減基数の補数に$+1$してあげたものが補数となるので、$11001$の補数は、$00110$に$+1$をした$00111$となる。確かに$11001+00111 = 100000$となって桁が上がっている。

3. 補数を使った減算表現

　準備が長かったが、これから「加算による減算」を見ていく。具体例として$253 - 121 = 132$(10進数)を使おう。

　さっそくではあるが、「加算による減算」の表現を見てみよう。まず、$121$の補数である$879$を$253$に足すと、$253 + 879 = 1132$となる。下三桁の$132$の値は、$253 - 121 = 132$の結果と合致する。これは、$253 + (1000 - 121) = 1000 + 132$と変形してみると分かりやすいかもしれない。

• $253 - 121 = 132$
• $253 + 879 = 1132$
• $253 + (1000 - 121) = 1000 + 132$

　次に２進数で見てみよう。$1110 - 0011 = 1011$を使う。$0011$の補数は$1101$。よって、$1110 + 1101 = 11011$となり、下四桁の$1011$は確かに合致している。同様に変形して見てみよう。

• $1110 - 0011 = 1011$
• $1110 + 1101 = 11011$
• $1110 + (10000 - 0011) = 10000 + 1011$

　これが「加算による減算」の表現だ。補数の性質をうまく使っている。実際には$1011 ≠ 11011$なので、減算と全く一緒というわけではない。しかし、これにコンピュータの仕組みを組み合わせるとうまく減算を表現できる。

4. コンピュータの仕組み

　以下のコンピュータの仕組みを使う。

• コンピュータの演算機能は加算機能のみであること
• 演算機能は限られたビット範囲の中で行われること
• 加算によって溢れた桁は捨てられること

　これらを使うと、「加算による減算」がうまくいく。上記と同じ例を使う。

• $1110 - 0011 = 1011$
• $1110 + 1101 = 11011$
• $1110 + (10000 - 0011) = 10000 + 1011$

ビット範囲が$4$ビットと限られていた場合、溢れた$5$ビット目は捨てられるので、$1110 + 1101 = 1011$がコンピュータ上では成り立つ。以上から、加算によって減算を表現できた。

5. おわり

　初めの疑問を出発点にして調べていくと、n進法の性質とコンピュータの仕組みがうまく組み合わされていていることを知ってとても感動した。コンピュータに加算器しかないことに対して減算器もつければいいのにと思ってしまったが、無駄をはぶいてシンプルでいるからこそここまでコンピュータは進化したんだろうと思わされた。

6. 参考文献

『プログラムはなぜ動くのか　第２版　知っておきたいプログラムの基礎知識』