ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

なぜ NOT + 1 が補数になるのか分かりやすく解説!

超長文ですから、ご注意ください。

サラサラッと読んでも構いません。

ただ、じっくり読まないと理解は出来ないかも知れません。


情報処理学(コンピュータの学問)で覚えるものに、補数というものがあります。

申し訳ありませんが、補数が何か分からない方はこの記事を読むの適していません。

まずは補数を覚えてください。


さて、数値の補数をとりたいときは、
その数値をNOT演算で反転させ、1を加算すればいいのですが、

なぜそれが補数になるのでしょうか

私が愛読している矢沢久雄氏の本でも補数が解説されているのですが、
「とにかくNOT + 1で補数がとれると覚えてください」みたいな書きかたがされていました。

もちろんNOT + 1で補数がとれることには理由があります。


そこで今回、私がNOT + 1で補数がとれる理由を、
チョー分かりやすく説明いたします!


追記: 実際、書いてみたら全然分かりやすくなくなりました。


では張り切って参りましょう!




まず、「なんで補数で引き算ができるんや」と疑問に思う方が多いと思います。

補数を覚えるとき、符号ビットがどうたらで11111111で…
なんて説明をされ、意味不明な1の並びを見させられます。

ここからどう引き算につなぐのか…。

さて、符号ビットとありますが、実は補数と符号ビットは関係ありません。

2進数で考えるからいけないんです。
実は10進数でも何進数でも補数は存在します。

10進数で話を進めていきましょう。



さてさて、何か引き算をやってみたいですね。
9 - 6をやってみましょうか。
答えは3ですね。


では、いきなりですが、106をします。
答えは4です。

では94を足します。答えは13でした。

そして、最後に10の位を無視します
要するに10引くんです。

さて、10の位を無視すると3が残りますね。

おめでとうございます!
9 - 6の答えと同じになりました。


…偶然ではありません。
96をお好きな数値に変えて計算してみてください。

偶然ではないことを示すために、96をアルファベットに変えます。



a = 任意の数値
b = 任意の数値
c = b以上になる10の整数乗


cが10の整数乗となるのは、話を補数につなげるためです。

今からいう等式を成り立たせるためだけなら、
cは本当はなんでもいいのですが、
それだと補数になりません。

また、cb以上になるのも話を補数につなげるためです。

とにかく、今はそういうルールがあるという事でやってください。


さて、この状態で、
a + c - b - c = a - bが成り立ちます。

実は、この等式が成り立つがゆえに、先ほどの計算ができたんですよ。


ところで、この等式が複雑で分かりにくいのですが、
式の中に + c- c が入っていませんか?

+ c- c が両方あると、その部分は0になりますから、
cのところを取り払って、

a - b = a - bに変換できます。

変換すると、当たり前のことを言っただけの式になりましたね。




先ほど9 - 6を、おかしなやり方で計算する例がありましたが、この式に当てはめてみます。


9 - 6をやりたいんですから、

a = 9で、
b = 6で、

そして、cb以上の10の整数乗ですから、
c = 10です。


では等式と同じやり方でいきます。

9 + 10 - 6 - 10 = 9 - 6ですね。

計算してみると、やはり等式は成立しています。

ところで現在、思いっきり引き算を使用していますから、
「コンピュータではどうするねん」とおっしゃるかも知れません。

しかし、なんとコンピュータでもこの計算ができるんです。
引き算ができるわけではありません。

式の 10 - 6 の部分、そして隣の - 10 の部分のみ、
減算不可能なコンピュータでも計算できるんです。

NOT + 1 とオーバーフローを利用して…。



さて、そろそろコンピュータの話に参らないといけませんから、
ここからはコンピュータで使う2進数で話を進めたいと思います。

しかし、ここでの例も 9 - 6 にしておきましょう。 

2進数で書くと 1001 - 110 です。


とりあえず、コンピュータで使うことを想定してサイズを揃えます。

1001 - 0110 にしました。

左のほうを0で埋めただけです。


アルファベットで言うと、現在

a = 1001
b = 0110


になっていますから、

c
b以上の10の整数乗…ではありません。

この場合、cb以上の2の整数乗です。

なぜ10から2になったのかと言うと、2進法に変わったからです。


等式を成立させるためだけならcはなんでもいいんですが、

数学式以外の方法で引き算をする「補数」としてやるなら
cはこのようなルールでやらないといけません。


ということは、
c = 1000です。

これで等式は成立します。

しかし、2進法でも引き算はしないといけません。

1000 - 0110 をやらないといけないのです。

つまり、2進法になってもコンピュータに
この計算をやらせる事はできないのです。



しかし、コンピュータはそれをやってのけました。


まず c - b をやってのけます。

どうやったのかと言うと、NOT + 1を使いました。


まず、NOT演算は分かりますね。
各ビットを反転、つまり1なら0に、0なら1にします。

0110なら、1001に変わります。

ところで、各ビットを反転させるということは、
各ビットを1から引いているということにお気づきですか。

各ビットを反転させるという事は、各ビットを1から引くという事と変わらない。 




 各ビットを反転させるという事は、
 各ビットを1から引くという事と変わらない。






確かにそうですよね。まぁ普通のことです。

ではさらにもう一つ、
各桁で各桁を引いて、あわせたときも、
全桁から全桁を引いたときも結果は変わらないことを覚えてください。

つまり、 1 - 0, 1 - 1, 1 - 1, 1 - 0 をあわせたものは、
1111 - 0110と変わらないんです。


数学的に書くとこうなる。
数学的に書くとこうなる。


そして、NOT演算は各ビット(各桁)1から引いているのだから、
それは 1111 - xxxx に変換できることが分かります。


つまり、NOT演算は1の並びから数値を引く演算だと取ることができます。

数学的に書くとこうなる。
数学的に書くとこうなる。

1つ目の画像で説明したことを、2つ目の画像で説明した法則にそって変換しただけです。

1の並び」というのがくせ者で、いくつ1を並べた数にすれば良いのでしょうか。

NOT演算をかける数値の、ビットのぶん並べます。

NOT演算をかける数値が1だったとしても、
その数値がbyte型(char型)なら 11111111 - 1 がNOT演算になりますし、
その数値がint型で格納されていたなら、1が32個並んだ数値から1を引いたものになります。

保存しているビットのサイズによるということです。

最終的にNOT演算は1の並びから、
数値を引くことと同じだと分かりました。



では、補数の話題に戻ります。

数学式での補数の取りかたを再び説明しますと、

a = 任意の数
b = 任意の数
c = b以上の2の整数乗
(2進法)

このとき、 c - b が補数で、
c - b + a から上位の桁を無視したものは a - b と等しくなります。

しかし、コンピュータの場合、引き算ができないため c - b が出来ないという問題と、
上位の桁を無視するというのが曖昧という問題がありました。

まず c - b ですが、これはNOT + 1で代用できます。

なぜかと言うと、(8ビットの型で説明)

先ほど、NOT演算は、11111111から引くんだと言いましたね。

cの条件を思い出すと、b以上の2の整数乗ですから、
bの型が8ビットだった場合、c100000000になります。

「なります」というより、100000000cの条件を満たしているんですね。

b = 1
とかだったら、cが大きすぎる感じがしますが、なんら問題ありません。

b以上ですから計算は可能です。

コンピュータでやる場合は桁を揃えたほうが便利なのです。


さて、 11111111 + 1 = 100000000 なのですから、
11111111 - b + 1 = 100000000 - b だというのは分かりますね。

ここがミソです。

11111111 - b はNOT演算と同じですから、
NOT b + 1 = 100000000 - b になります。


さらに100000000cですので、
NOT b + 1 = c - bです。

c - bbの補数ですから、

つまり、巡りまわってNOT b + 1bの補数なんですね。

このあと、NOT b + 1で、- bと同じことができるかどうか
実証しますが、とりあえず理論はこれで終わりです。



では実際に計算してみましょう。

int型で11111111111…なんて書いていられないので、
8ビットのbyte、char型にします。

それでも多いくらいですけどね…。


20 - 6 = 14 ですが、コンピュータでは補数で計算します。

コンピュータでは - 6 を、 + 6の補数 で代用します。

6は、byte型のデータ(2進数)では00000110になります。

さて、NOT + 1で11111010にして、補数をとりました。

数学的に言うと、この数値は250なんですが、
コンピュータの世界では -6 として扱います。

結果として -6 と同じ結果をもたらすからです。

あくまでもこの数値は250です。

さて、6の補数を20に足したら、20 - 6と同じ結果になります。
やってみましょう。

20はbyte型のデータ(2進数)では00010100になります。

00010100 + 11111010 = 100001110

100001110は、2進数では270ですが、
byte型を超えてしまっていますから、超えたぶんは無視されます。

コンピュータではそういう設計ですね。

「じゃあ270でも格納できるint型にすれば無視できへんやないか」とおっしゃるかもしれませんが、大丈夫です。

int型で計算する場合は、補数を取る段階で、もっと1が並びますから、
絶対に桁あふれするようなっています。

するとbyteのときと同じになります。

(記事のだいぶ前に、「上位の桁を無視するのが曖昧」とありましたが、“コンピュータのデータは有限”という性質を生かして解決しました。)



さて、超えたぶんを無視すると00001110になります。

10進数にしてみると、14です。

やりたかったのは 20 - 6 ですから、補数で本当にやることができました。

つまり、補数で引き算が出来るのです。
(これは前から知っていましたね…。)



今まで考えてきた補数の概念は、やはり正解でした。

NOT + 1というだけでも、細かく仕組みを探ると、大変な長文になります。

昔のコンピュータの設計者たちは、このことを自分で考えたのですから凄いです。

説明するだけで一苦労ですからね。


NOT + 1が補数になる理由は、以上で説明したつもりです。

分かりにくい説明でしたが、理解していただけると幸いです。

それでは、やっと記事を終わります。

tag:

コメント

確かに補数で何故引き算ができるのか疑問になりますよね
ノイマンの頭の中は余裕なんでしょうねww

  • 2013/01/28(月) 22:45:14 |
  • URL |
  • Raldy #-
  • [ 編集 ]

Re: Raldy

ノイマンの頭は特別ですからね(笑)
ちなみに「補数でなぜ引き算ができるのか」ではなく、「なぜNOT + 1で補数になるのか」です。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/229-3590fba4
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。