負の整数を扱うマイクロプロセッサのロマンス ― CPU算術設計の方法とその理由

コンピュータについて最初に学ぶことのひとつは、コンピュータが理解できるのは0と1、すなわちビットだけだという事実です。

一方、私たち人間は10進法で数をやり取りします。この体系では0から9までの数字を使い、プラス記号(+)とマイナス記号(-)で正負を表します。

しかしコンピュータが使えるのは0と1という2種類の数字だけです。そこで昔の技術者や数学者たちは、負の数を表現し、それを使って演算を行うための巧妙な手法を考案しました。今回はその手法の美しさを探っていきましょう。

まずはコンピュータの仕組みから

ソフトウェア、画像、テキスト、動画、数値など、あらゆるものは、コンピュータ内では最終的に0と1として扱われます。

画像・テキスト・動画・数値には、それぞれを0と1へ変換するためのエンコーディング方式が存在します。たとえばテキストならASCIIやUnicodeが有名です。

私たちが書いたプログラムは、コンパイラやアセンブラによって0と1の列に変換されます。この0と1の集合は機械語(マシン命令)と呼ばれ、プロセッサが実行する前に、まずコンピュータの主メモリ(RAM)に格納されます。

プロセッサは主メモリから命令をフェッチ(読み出し)することで実行サイクルを開始し、次にプロセッサの制御ユニットがその命令を2つの部分――オペコード(操作コード)とオペランド――にデコード(解読)します。

オペコードは、ADD(加算)、JMP(ジャンプ)、INC(インクリメント)など、実行すべき動作を決定します。オペランドは、その操作の対象となる値(またはメモリ位置)です。

解読された命令は、実行のためにALU(演算論理装置)へ送られます。ALUではオペコードに基づいてオペランドに対して命令が実行され、結果は再びメモリに書き戻されます。

たとえばアセンブリコード ADD eax, 42 は、まずアセンブラによって機械語(0と1)に変換され、フェッチ・デコード・実行サイクルが始まる前に主メモリへ格納されます。

ADD eax, 42 の機械語のフェッチが完了すると、命令はデコードされます。その結果、オペコードは ADD、オペランドは eax と 42 であることが分かります。

eax はレジスタです。レジスタとはプロセッサ内部に組み込まれたメモリ位置で、プロセッサが瞬時にアクセスできます。eax レジスタは多くのプロセッサで「アキュムレータ」と呼ばれています。

ADD eax, 42 というアセンブリコードは、eax レジスタ(アキュムレータ)の現在の値に42を加え、その合計を eax に格納するよう設計されています。つまり eax = eax + 42 ということです。

仮に現在 eax が20だとすると、ADD eax, 42 を実行した後の eax の値は 20 + 42 = 62 になります。

EDVACのような初期のコンピュータの設計は、面倒な数学計算をより簡単に、より速くしたいという願いから始まりました。

コンピュータに計算させる責任のすべては、加算器(adder)――2つの数を足す回路――の肩にかかっていました。減算、乗算、除算といった高度な演算も、その回路の中で加算器を利用しているからです。

結局のところ、コンピュータとは論理機能を持つ高速な算術マシンにすぎません。2進算術(特に負の整数)の設計における課題と美しさを理解することは、CPUにおける最も基本的な概念のひとつなのです。

まずは10進数が2進数でどう表現されるのか、そして2つの2進数をどう足すのかを見てみましょう。その後、本題の「美しさ」に入っていきます。

2進法の仕組み

「872500を読み上げて」と言われたら、あなたはおそらく「87万2500」と答えるでしょう。頭の中で何が起きているのか見てみましょう。

右端の桁を一の位、その隣を十の位、さらにその隣を百の位とし、以下同様に10の累乗ごとに桁が増えていきます。

各桁の10の累乗が、その桁の「重み」です。百の位の重みは100です。各桁の数字にその桁の重みを掛け、すべてを合計すると完全な数になります。

上の図では、各桁の重みが 10^0 から始まって 10^5 まで10の累乗で増えていく様子が分かります。これこそが10進法が「基数10の体系」と呼ばれる理由です。

2進法では、各桁の重みは2の累乗で増えていきます。つまり重みは 2^0 から始まり、2^n まで続きます。これが唯一の違いであり、それ以外の仕組みは10進法とまったく同じです。各桁の数字にその桁の重みを掛けて合計すれば、元の数が得られます。

2進数の加算方法

2進数の加算は、10進数の場合とほぼ同じ要領で行えます。例を見てみましょう。1101(13)と 1100(12)という2つの2進数を足します。

10進法と同じように、一の位(2^0)から始めます。1 + 0 = 1 なので、そこに1を置きます。順を追って説明するので、全体像がつかめるまで読み進めてください。

0 + 0 = 0。次へ進みます。

1 + 1 = 2 ですが、2進法での2は 10 と表現されます。そこで繰り上がりの1を次の桁へ送り、現在の桁には0を残します。これは10進法の加算である桁が9を超えたときと同じ考え方ですね。

ここには1が2つあり、さらに前の桁からの繰り上がりが1つあるので、合計3つの1があります。その和は3で、2進法の3は 11 なので 11 と書きます。最終結果は 11001、つまり10進数で25となり、確かに13 + 12 です。

上の計算では結果を保存するために5ビットが使える前提でした。もし4ビットのコンピュータでこの加算を行うと、結果を保存できるのは4ビットだけです。

その5ビット目は4ビットコンピュータではオーバーフローと呼ばれます。整数演算ではオーバーフローのビットは無視されるか破棄されます。つまり4ビットコンピュータでは結果は 1001(9)になっていたはずです。

2進算術設計の美しさ

先へ進む前に、押さえておきたい重要な用語が2つあります。最下位ビット(LSB)と最上位ビット(MSB)です。

最も右側のビットが最下位ビットです。桁の重みが最小(2^0)だからです。そして最も左側のビットが最上位ビットで、桁の重みが最大(2^7)だからです。

もし世界に正の数しか存在しなければ、この記事はここで終わりでした(10進数の2進表現と2進加算の方法はすでに学んだからです)。

幸いなことに、私たちには負の数もあります。

CPUの算術設計の美しさは、まさにこの「負」にあるのです。

では、コンピュータは負の数をどのように表現し、負の数の演算はどう行われるのでしょうか? この問題へのエンコーディング方式を見ていきましょう。

なお、以降のセクションでは概念を理解しやすくするため4ビットのコンピュータを想定します。つまり5ビット目はオーバーフローとして扱います。同じ原理は16ビット、32ビット、64ビットなど、あらゆるCPUアーキテクチャの演算にも当てはまります。

符号絶対値方式(シグネッド・マグニチュード)

このエンコーディング方式では、1101 は10進数で -5 を意味します。左端、つまり最上位ビットが符号ビットです。符号ビットはプロセッサに数の符号――正か負か――を伝えます。

符号ビットが 0 なら正の値、1 なら負の値を表します。残りのビットが実際の大きさ(絶対値)を示します。

1101 の場合、符号ビットは 1 なので負の数です。101 は10進数で5なので、1101 は10進数で -5 となります。

上の図は、このエンコーディング方式で4ビットが表現できるすべての整数を示しています。ここまでは順調に見えます。

しかしよく観察すると、この方式には非常に深刻な設計上の問題があることが分かります。その問題と向き合ってみましょう。

正の数と負の数を足してみます。たとえば +4 と -1 です。答えは (+4) + (-1) = (+3)、つまり 0011 になるはずです。

ところが、結果は 1101(-5)になってしまいました。本来の答えは 0011(+3)のはずです。この方式をプロセッサに実装するなら、この問題に対処するための追加ロジックが必要になります。しかし技術者はロジックへの複雑さの追加を嫌います。

回路を追加すれば消費電力は増大し、性能も低下します。

トランジスタベースの現代のコンピュータにとっては些細な問題に思えるかもしれません。

しかし、数千本の真空管で動作し、キロワット単位の電力を消費し、数百人の人が日々運用していたEDVACのような初期のコンピュータを思い浮かべてください。政府はその構築に数百万ドルを投じました。

当時、回路や真空管を追加することは、数千ドルの出費と深刻な保守トラブルを意味したのです。

そこで技術者たちは、より賢いエンコーディング設計を考える必要がありました。

さあ、この問題を解決し、システムをよりシンプルに、より高性能に、より省電力にする「美」の時が来ました。

美しいエンコーディング方式の登場 ― CPUが輝く瞬間 ❤️

このエンコーディング方式でも、前の方式と同様に左端のビットが符号ビットとして機能します。ただし、負の数を表現するために少し工夫が施されています。

正の数は前の方式とまったく同じ方法で表現されます。先頭の 0 に続き、残りのビットで大きさを表します。たとえばこの方式でも6は 0110 と表現されます。

負の数を表現するには、その正の数に対して2段階の数学的処理を行います。つまり -6 を表現するには、+6 に対して2段階の処理を施して2進数の -6 を得るのです。

-6 がどのように2進数へエンコードされるか見てみましょう。

前の符号絶対値方式では、+6 の負の値を求めるには、単純に符号ビットを 0 から 1 に変えるだけで済みました。0110(+6)は 1110(-6)になるはずです。

新しいエンコーディング方式では、まずビットを反転させます。0を1に、1を0に変えるのです。0110(+6)は 1001 になります。このビット反転は「1の補数(one's complement)」と呼ばれます。ここで 0110 の1の補数として 1001 を計算したわけです。

次に、1の補数に1を加えます。1001 + 1 = 1010。この 1010 が、新しいエンコーディング方式における -6 の2進表現です。この方式は「2の補数(two's complement)」と呼ばれます。

つまり、正の整数の2の補数を計算すると、その負の対応値が得られるのです。

ビットを反転すると1の補数が得られます。1の補数に1を加えると、最初のビット列の2の補数が得られます。シンプルでしょう?

さて、このエンコーディング方式がなぜ美しいのか見てみましょう。0100(+4)と 1111(-1)を足してみます。

ご覧ください。2の補数方式では正確な結果が得られます。これで符号を気にせずに整数の加算ができるようになりました。

私たちは、負の整数が2の補数エンコーディングによって0と1で表現できることを学びました。では、ADD eax, -3 を実行し、eaxレジスタの現在の値が -1 だったとしましょう。ADD eax, -3 実行後のeaxの値は -4(2の補数エンコーディングでは 1100)になります。

オペレーティングシステムがeaxから 1100 を取り出してユーザーに結果を提示するとき、OSは 1100 を10進数へどうやってデコードするのでしょうか? あるいは、プログラマである私たちが 1100 を見かけたら、それがどんな数を表しているのかどうやって判断すればいいのでしょうか?

もちろん、1100 に一致するまで各正の整数の2の補数を計算し続けることはできません。あまりにも遅すぎます。

プログラマやOSは、2の補数の美しい性質を利用して2進数を10進数へデコードします。

正の数の2の補数を計算すると、その負の対応値が得られます。実はその逆もまた真なりです。つまり、負の数の2の補数を計算すると、その正の対応値が得られます。その理由はすぐ後で説明します。

まず、OSやプログラマが 1100 を10進数へどうデコードするのかを理解しましょう。

eaxレジスタから 1100 を取り出すと、OSは符号ビットとして 1 を確認し、この整数が負であることを認識します。1100 の2の補数を計算すると、その正の対応値である 0100(+4)が得られます。OSはその正の値にマイナス符号を付けて、最終的な答えとして -4 を返します。もう一度この段落を読み直すと、理解が深まるはずです。

こうしてCPUは微笑み、「今日の美との別れ」を告げるのです ;)

CPUは母親に会いに家へ帰りました。今はたっぷり時間があります。2の補数という芸術の内側の仕組みについて語りましょう。

なぜ、どのように2の補数エンコーディングは機能するのか?

ある数、たとえば +42 の負の値を求めろと言われたら、最も簡単な方法は何でしょうか?

おそらく最も簡単なのは、その数を0から引くことですよね?0 - (+42) = -42。これを繰り返せば正の値に戻ります。0 - (-42) = +42。2の補数は、まさにこの数学の上に築かれているのです。

ここでは 10000(左端の1はオーバーフローなので10進数では0)から 0101(+5)を引いています。結果は 1011、つまり2の補数エンコーディングで -5 です。減算の具体的なやり方は気にしないでください。それは重要ではありません。大事なのは2の補数の背後にある直感です。

10000 は 1111 + 0001 と書けます(この2つを足すと 10000 になることを試してみてください)。つまり実際に行っているのは:

        10000       -   0101
=>  (1111 + 0001)   -   0101

この式を整理すると:

    (1111 + 0001)  -  0101
=>  (1111 - 0101)  +  0001

Step 1: subtract 0101 from 1111

        1 1 1 1
       -0 1 0 1
       ---------
        1 0 1 0
        
       see, subtracting 0101 from 1111 is equivalent 
       to inverting the bits of 0101, as we got 1010 as a result. 

  
       
Step 2: add 0001 to the above result  

        1 0 1 0  ---> result of step 1
       +0 0 0 1
       ---------
        1 0 1 1      
       
       we get 1011 that is -5 in two's complement encoding.      

お分かりでしょうか? 2の補数の仕組みは、根本的には「0からその数を引く」ことを行っています。ビットを反転して1を加えることは、0から数を引くための速くて賢い方法なのです。

だからこそ、ある数の2の補数を計算すると、正の数なら負の値が、負の数なら正の値が得られるのです。実際には 0 - number を計算しているからです。

1900年代のコンピュータは加算の演算ロジックしか持っていませんでした。2の補数エンコーディング方式があまりに美しいので、減算も簡単に実行できたからです。

たとえば100から12を引く場合、CPUは +12 の2の補数を計算して -12 を作り出し、それを100に加算します。これで必要な出力が得られます。

それは、減算が遅く複雑なプロセスだからです(借り入れの処理のおかげで)。その道を選ぶなら、コンピュータには高価な減算回路が必要になります。負の整数を表現するたびに毎回0から引き算することを想像してみてください。私たちにとっても、コンピュータにとっても悪夢です!

2の補数エンコーディングは、より高性能なソリューションであり、シンプルな回路設計につながり、多大なコストを節約します。高価な減算回路が不要になり、正負の整数の演算に対処する追加ロジックも必要ありません。単純な加算だけで、加算と減算の両方が実現できるのです。

だからこそ、この美しいエンコーディング方式――2の補数 ❤️――を設計したコンピュータ設計者たちに感謝しましょう。

まとめ

私は、自分が制作する学習教材に対してお金を請求しないと心に誓っています。教育のために行うことは、簡単な記事であれ、講座であれ、電子書籍であれ、常に100%無料で公開すると決めています。

Twitterアカウントでは役立つリソースを投稿し、有意義な考えを共有しています。この記事から何か新しいことを学べたなら、フォローしてDMを送っていただけると嬉しいです。きっと最高の一日になります :)

すべての開発者、すべての著者、そしてすべての人は、誰かから学んで成長します。優れた人々やリソースから学んだ知識は、引用され広められるべきだと私は信じています。それが良いものをより多くの人へ届ける原動力になるのです。