へっぽこびんぼう野郎のnewbie日記

けろけーろ(´・ω・`)! #vZkt8fc6J

2の補数と1の補数についての混同と混乱について

ノイマンが書いた本を読んでたら減算器の話について出てきて思い出した。

そういえば1の補数っていうのややこしいなと。なのでブログに書いておくことにした。

要求知識

最低限理解に必要な知識として

・ビット
・2進数、10進数
・コンピュータは電子回路で動いていることを知っている

などを要求しています。

突如出現! 1の補数!

2の補数 について説明されるとき、まず補数とはなんぞやという話から始まって、たいてい次のような話が出てくるように思う(読み飛ばしていいです)

補数というのは足すと繰り上がりが発生する数のことだ。
たとえば10進数のとき、3に対する10の補数は7である。4に対する10の補数は6だ。
3に対する9の補数は6だ。
2進数で考えてみよう。1に対する2の補数は1だ。1に1を足したら10になるからだ。0に対する2の補数は0だ。
1101に対する2の補数は0011だ。

なぜこんな補数という概念ができたかというと足し算を使って引き算ができるからだ。
どういうことだろう。1101に0011を足すと10000になるということはビットを反転させると引き算になるからだ。それに最近コタツがほしいと思っている。

1101のビットを反転すると0010になる。ここに1を足すと0011という数字が得られる。つまり10000-1101は、1101をビット反転してそこに1を足したものと同じというわけだ。
この1101のビットを反転してあと1を足せば繰り上がる数(この場合は0010)のことを1の補数という。

こんな感じでなんとなく煙に巻かれる。

ふつうの人類はこのように考える。

しかしそれにしても 1の補数 とはなんだろう。

補数は繰り上がる数 とか言ってたな。

足すと繰り上がりが発生する数? 1進数? 1進数の繰り上がり?

2の補数とは?

というふうに考えて頭がパンクしてしまうはめになる。

本には詳しく書かれておらず、突然「1の補数を使います」とさっきの意味の補数っぽい感じでババンと用語が出現し、あとは「ま、まあわかるよね」というような感じでスルーされている。

こうしてコンピュータは難しいと言われ初心者は死んでいった。

2の補数と1の補数についての驚きの事実

そして、おどろきの事実はこうだ。

2の補数は足すと繰り上がる数だけど、1の補数は足してもべつに繰り上がらない。

補数って言ってるけどおんなじ意味の補数ではない。

メロンパンとジャムパンにおけるパンの違いぐらい違うものだと思っていい。

(メロンパンとジャムパンのそれぞれのパンの部分は、パンはパンでも、全く同じ種類のパンではないという意味)

結局、2の補数と1の補数とは何か。

・足すと2^nになる数を2の補数と呼ぶ。
・足すと2^n-1になる数を1の補数と呼ぶ。

つまり2の補数から1を引くと1の補数になる。まじでそれだけである。

ナ、ナンダッテー!? ソレダケカァ!?

補数という言葉に疑問を持つと死ぬ。そういう罠だったのだ。

厳密には

2の補数 = 2進法における基数の補数(radix complement)
1の補数 = 2進法における減基数の補数(diminished radix complement)

という。

「俺らコンピュータの勉強やってるんだから2進数における減基数の補数って言うのだるいし、2進数なのは当たり前だし今後は1の補数って呼ぼうぜ」
「おっ、そうだな。100に対する1の補数は11!」

くらいに略された言葉だ。

それから「1の補数」は英語では ones' complement で、厳密には「1たちの補数(足すと全部1になるから)」であり、「2の補数」は two's complement だ。

one's complement ではないので注意!!!(でも one's complement って書く人の方が多いよ!おまえらふざけんなよ)

いったい、これによってどのくらいの人数の人が苦しみを味わったのだろうか。

ともかく、 2の補数と1の補数は、メロンパンとジャムパンくらい違う という気付きは大事だ。

ちなみに 6に対する10の補数は4 と言うべきところを 6の補数は4 というように間違って言う人もいる。適当なことを言うんじゃねえ。

補数の重要性

それでまあ、この二種類の補数という概念がだいじなのは「足し算を使って引き算したいから」という欲求があったからだ。

その昔、初期の頃、人類は電子回路では足し算しかできなかった。足し算しかできないように作っていたので、足し算しかできなかった。

そこで頭のいい人が「足し算使って引き算すればいいじゃん」と考えた。

これはすごいことだ。足し算しかできなかったら、ふつうの人間は「足し算しかできねえのかよ」と言いつつも、足し算にしか使わないし、もしかしたら「コンピュータとかいうの使うより人間が計算した方が早いじゃん。科学者はバカ」とか言い出すものだ。

なのでこれは「仕事ができないやつを組み合わせて仕事が回るようにする」くらいの発想だ。

それで、まあそういう寓話は置いといて、その人は引き算もしたがっていた。

そもそも引き算というのは何をしているのか。

2進数だと 1 + 1 = 10 だから 10 - 1 = 1 で、 10 + 1 = 11 だから 11 - 10 = 1 だ。足し算の逆のことをしている。

ところでコンピュータを作るために色んな論理回路が必要になる。論理回路にはNOT回路とかいうものがあって、これはビットを反対にするものだ。これを使って引き算が作れる。

01 のビットを反転させると 10 になる。反転させたあと1を足して、

10 - 110 + 10 + 1 のように書き換えてしまう。

そして 101 という答えが出るけど、3桁目の1は消して 01 というふうになる。

こうすると 10 - 1 = 1 ができたことになる。なぜか。

10 - 110 + (11 - 1) + 1 - 100 と等価だからだ。ビット反転という操作は 11 - 1 という部分に相当する。そして3桁目を脱落させた操作は、 -100 に相当する。

このようにして m - ncutOverflowedOne(m + invert(n) + 1) と等価というふうにできる。

そんなかんじです。いやあ補数って便利だなあ。

なんか煙に巻いてる気がするけど、このビット反転(invert)が要は1の補数を求めてる箇所です。そのあと1の補数に +1 して 2の補数を求めてます。

トランジスタでも買ってきて減算器を作ればすごいわかるようになると思います。

そのうちつくったら追記します。