コグノスケ

何を補うの？

毎回話題がバラバラな日記ですみません。今日は補数の話です。

N進数の補数は2つあります。Nの補数と、N-1の補数です。10進数ならば10の補数と10-1の補数（9の補数ともいう）があります。

N進数における二つの補数

あるN進数xの Nの補数yとは、足すと桁上がりする最小の数値を指します。
10進数でいきますと、x = 123だとしたら、10の補数は足すと桁上がり（1,000になる）する最小の数値ですから877です。

要するにy = 1,000 - x = 1,000 - 123 = 877と計算します。4桁の数字なら10,000から引けばいいですし、5桁なら100,000から、n桁なら10^(n) から引いてください。

あるN進数xの N-1の補数zとは、足しても桁上がりしない最大の数値を指します。
また10進数を例に取ると、x = 123として、10-1の補数は足しても桁上がり（1,000）に達しない最大の数ですから、876です。足すと999になります。

これも要するにz = (1,000 - 1) - x = 999 - x = 876と計算します。特徴として、10の補数から1引いても得られますし、逆に10-1の補数に1を加えると10の補数になります（この性質は後ほど重要です）。

補数の活用方法

Nの補数は何が嬉しいかというと「負の数の表現として使えば、引き算が不要になる」という点です。

3桁の10進数500 - 300を計算したいとします。「引き算は知らないが3桁の足し算と10の補数を書いた表だけ持ってる」と仮定します。むちゃくちゃに見えますけど、後で意味が分かると思います。

引き算は知りませんので、まずは負の数を消しにかかります。負の数は絶対値の補数に置き換えて消します。表を見ると300の10の補数は700（計算で出すなら1,000 - 300）ですから、
500 - 300 = 500 + 700
こう置き換えます。すると足し算のみになって、計算できるようになります。
500 + 700 = 1,200
4桁目が出てきてしまいましたが、3桁の足し算しか知らんので4桁目は捨てます。さようなら〜。
1,200 => 200
この結果は500 - 300 = 200の結果と一致します。

不思議に見えますが、そもそも補数yの定義がy = 1,000 - xなので、x = 300で式を展開すると、
500 + (1,000 - 300) = 1,200 --(4桁目無視)--> 200
となるのは当たり前といわれれば当たり前の結果です。しつこいですが大事なポイントは「引き算が足し算に化ける」という点です。

2進数だと非常に嬉しい

とはいえ、10進数だと補数を計算するために結局引き算が必要で、ありがたみがありません。これはその他の記数法（図では3進数を例とした）でも同じです。

3進数と3の補数、3-1の補数

ところが2進数となると非常に嬉しい性質があります。以下の図を見てください。

2進数と2の補数、2-1の補数

2進数においては全桁を反転させる演算（Not演算）によって、容易に2-1の補数を得ることができ、そこに1加えれば2の補数を得ることができます。つまりNot演算さえあれば2の補数の導出に引き算は不要です。コンピュータだからこそできる技といえましょう。

この性質のためコンピュータに減算器は不要で（※）、加算器の前にNot演算と1加える回路をつけるだけで良いのです。回路が少なくなればコンピュータも安くなります。いやあ、補数って素晴らしいですね。

（※）コンピュータは前章の説明に出てきた「引き算は知らないが3桁の足し算と10の補数を書いた表だけ持ってる」の代表格です。コンピュータの場合2進数を扱うため10の補数ではなく2の補数です。
まとめると「一定桁（32桁、64桁など）の足し算と、2の補数しか知らない」変な奴と言えます。本当は意図的にそう作っていると言った方が正しいですけど…。

負の数を解釈

補数を負の数として扱うと良いこと（減算がなくなる）があるのは分かっていただけたかとおもいます。残る問題はどこからを負の数と見なすかです。卑近な例で言うとprintfしたときに、どこからマイナスなのよ？って話です。

前章まで話してきた計算の問題と関係ありそうに見えますが、実は全然関係ありません。ぶっちゃけた話、どこから負の数と見なしても構いません。以下の図をご覧下さい。

2進数から10進数へ解釈する一方法

この図にある解釈方法ですと2進数の101以上を負の数と見なします。

• 101未満の数を表示しなさいと言われたら、そのまま10進数に変換した値を印字します。
• 101以上の数を表示しなさいと言われたら、補数をとって10進数に変換した値と、マイナスの符号をともに印字します。

例えば110を渡されたら、101以上なので補数を取って010とし、010を10進数にすると3なので、-3と表示します。

何？ずれてる？いやいや…。このような解釈でも使っている人がウンと言えばそれで良いんです。とはいったものの、この方式ではウンと言う人は少なそうです。この方式は欠点が多すぎます。

桁が増えたときに正負の境界をどう決めるかがあいまいであるがために、境界を見分ける処理が複雑になる可能性があります。プログラマや回路設計者に嫌われますね。それとやたら正の数ばかりが多くて、負の数を使いたい人にも嫌われます。

良い解釈方法はあるか

多くの方が見慣れたパターンは、最上位のビットが1なら負の数と見なす、以下のような解釈方法でしょう。

2進数から10進数へ解釈する効率的な方法

この解釈方法が採用されている理由は、効率的だからだと思われます。この解釈方法であれば、何桁になろうとも「最上位ビットの有無」という同じルールが適用できます。さらに正の数の範囲と負の数の範囲がほぼ同じ（負の数の範囲が1広いけど）で使いやすいのです。