Simplestar Game
since 17/01/2009
:::::::::::013話 2進数と算術演算:::::::::::
どうも，星姫でーす．
こ，今回の目標は2進数での計算方法を学び，各命令の速さを知ることです．
前回を読んでから時間が経った人は，もう一度読みなおして用語を確認することをおススメします．
機械語を扱うのは今回が最後となりますので，早くプログラミングをやらせろと言う方も，基本ですから，お付き合い願いたいです．
-----------------------------------------------------------------------------------------------------------------
「コンピュータ・ハードウェアにおいて四則演算はどのようにして行われるのか」という「謎」を今回は解き明かします．
混同を避けるため，2進数の表現を右側に(2)，10進数の表現を右側に(10)と表記します．
まずは 32bitを最後まで数えてみます．はい，0,1,2...
0000 0000 0000 0000 0000 0000 0000 0000 (2) = 0 (10)
0000 0000 0000 0000 0000 0000 0000 0001 (2) = 1 (10)
0000 0000 0000 0000 0000 0000 0000 0010 (2) = 2 (10)
0000 0000 0000 0000 0000 0000 0000 0011 (2) = 3 (10)
… … …
1111 1111 1111 1111 1111 1111 1111 1100 (2) = 4,294,967,292 (10)
1111 1111 1111 1111 1111 1111 1111 1101 (2) = 4,294,967,293 (10)
1111 1111 1111 1111 1111 1111 1111 1110 (2) = 4,294,967,294 (10)
1111 1111 1111 1111 1111 1111 1111 1111 (2) = 4,294,967,295 (10)
単純に対応付けを行えば，32bitで表せる最大の整数は上記のように43億弱となります．
負の符号が付かないこの表現を符号なし(unsigned)表現と言います．
加算と減算
とりあえず，符号なし整数の加算と減算を見てみましょう．
足し算は，小学校で習う筆算と同じです．2進数はさらに難易度が低く，頭の悪いコンピュータにも簡単にできます．
0011 0101 (2) = 53 (10)
0001 0110 (2) = 22 (10)
加算結果 ↓
0100 1011 (2) = 75 (10)
小学校の計算ドリルを思い出します．義務で幼少期に習わされる部分なので説明を省きます．
ここが理解できない人は，正直厳しいです．
さて，コンピュータは足し算しか出来ないのに（第10話），減算はどうするのでしょうか？
キーワードは2の補数(two's complement)表現です．下記を数えてみて下さい．
0000 0000 0000 0000 0000 0000 0000 0000 (2) = 0 (10)
0000 0000 0000 0000 0000 0000 0000 0001 (2) = 1 (10)
0000 0000 0000 0000 0000 0000 0000 0010 (2) = 2 (10)
0000 0000 0000 0000 0000 0000 0000 0011 (2) = 3 (10)
… … …
0111 1111 1111 1111 1111 1111 1111 1101 (2) = 2,147,483,645 (10)
0111 1111 1111 1111 1111 1111 1111 1110 (2) = 2,147,483,646 (10)
0111 1111 1111 1111 1111 1111 1111 1111 (2) = 2,147,483,647 (10)
1000 0000 0000 0000 0000 0000 0000 0000 (2) = -2,147,483,648 (10)
1000 0000 0000 0000 0000 0000 0000 0001 (2) = -2,147,483,647 (10)
1000 0000 0000 0000 0000 0000 0000 0010 (2) = -2,147,483,646 (10)
1000 0000 0000 0000 0000 0000 0000 0011 (2) = -2,147,483,645 (10)
… … …
1111 1111 1111 1111 1111 1111 1111 1100 (2) = -4 (10)
1111 1111 1111 1111 1111 1111 1111 1101 (2) = -3 (10)
1111 1111 1111 1111 1111 1111 1111 1110 (2) = -2 (10)
1111 1111 1111 1111 1111 1111 1111 1111 (2) = -1 (10)
単純にとらえるなら，赤で示した最上位ビット(most significant bit)が1の時，負，対して0の時，正ということになります．
試しに，1 - 1 = 0 を見てみましょう．
0000 0000 0000 0000 0000 0000 0000 0001 (2) = 1 (10)
1111 1111 1111 1111 1111 1111 1111 1111 (2) = -1(10)
加算結果 ↓
0000 0000 0000 0000 0000 0000 0000 0000 (2) = 0 (10)
最後に繰り上がるケタは，レジスタに収まりきらないので切り捨てられます．よってこんな不思議な現象が起こります．
興味湧きました？この補数表現により，加算回路で減算が可能となるのです．
補数の求め方ですが，0と1を反転させて，お互いを足し合わせると-1になるルールを利用します．
例えば，0... 0101 (2) = 5 (10)の補数を知りたければ，0と1を反転した1... 1010 (2) がルールより -6 (10)であると判断でき
1を足した結果の 1... 1011 (2) が -5(10) と簡単に求められるのです．
こうして，最大で表せる整数は21億強と符号なし表現と比べて半減しましたが，負の表現が可能となりました．
このように正負を扱える表現を符号付き(signed)表現と言います．
ここで，signed と unsigned の本質的な違いを理解できるようになりました．
以下，ちょっとした用語の説明です．
演算結果がレジスタに収まりきらない場合，正しい結果を表現することが出来ません．
この現象をオーバフローと呼んでいます．
ケタに限界を設けた時点で，例外が発生してしまうということです．
この先プログラムを触っていけば，必ずバグに出くわす事になるでしょう．
符号付き，符号なし表現について困った時は，今回学んだことを思い出してほしいと思います．
四則演算について加算と減算の説明が終わりました．残るは乗算と除算ですね．
乗算について
九九を例に，掛け算の実現方法について話をしていきます．まずは，8×9を考えてみましょう．
1000 (2) = 8 (10)
1001 (2) = 9 (10)
乗算結果 ↓
1001000 (2) = 72(10)
どのように人間は計算しましたか？九九を確かめるには，小学2年生の記憶ではなく，足し算ですよね？
8を9回足し合わせます．8+8+8+8+8+8+8+8+8 (10) = 72 (10)です．
では 2進数も同じように 1000 (2) を 1001 (2) 回足し合わせるのでしょうか？
1000 + 1000 + 1000 + 1000 + 1000 + 1000 + 1000 + 1000 + 1000 (2) = 1001000 (2)
確かに，同じ結果になりましたね．
一応，加算回路のみを用いて乗算が実現できることを理解できると思います．
実際はもっと高速に計算できるように，計算手順（アルゴリズム）が工夫されています．
上記のやり方だと，32bitをフルに使った42億×42億の計算は42億回も加算を行わなければいけないもんね！
今のところ，32回の加算で解決できるようになっています．（教科書参照 p167）
この32回の足し算のために32個の加算器がCPUには用意されていて
加算と減算に比べ，大して速度を落とさずに乗算を行えるようになってます．
え！？加算より高速な乗算！？
はい，シフトという作業で，ケタをずらすことを行うだけで，2倍，4倍，8倍，16倍…と
2の累乗倍の結果が得られるので，式の書き方により，加算より高速に乗算を行うことができたりします．
一般に遅い処理の除算についても，シフトを利用した2,4,8,16…で割る作業に変えることで処理が高速になります．
覚えておくと，いつか高速化の問題で悩んだ時に，役立つかもしれません．
除算について
最後に割り算について説明します．
これまた，例として 1001010 (2) = 74 (10) 割ることの 1000 (2) = 8 (10) を行ってみます．
割り算についておさらいします．
これから割ろうとする74(10)を被除数，割る数8(10)を除数，求められるのが商と剰余です．
これらについて 被除数 = 商 × 除数 + 剰余 の式が成り立ちます．以下の筆算を見て下さい．
1001010 (2) = 1001 * 1000 + 10 (2) と商と剰余が求められました．
ケタをずらす，引き算をする，正負を確かめる，この三つの組み合わせで除算が成り立ちます．
よって，シフトと加算，条件分岐だけで除算ができることを理解できます．
この条件分岐がくせ者で，高速なアルゴリズムが組めない原因になってます．
ここで，除算は乗算ほど高速化が望めない演算なのだと，覚えておきましょう．
最後に…
ここまでお付き合いいただき，ありがとうございました．
プログラミング基礎編は以上で終了です．
次回からは，実践編です！
いよいよ「初心者」の仲間入りです．
これから始まる，無数のトライ＆エラーにご期待下さい．
2009/10/04 初記．
2009/10/18 追加．