コンピューターの掛け算と割り算
この記事ではコンピュータの掛け算と割り算に使われるシフト演算の説明と計算をします。筆者が情報数学の基礎を勉強していて「すげー」と思った部分を書いているので間違っている点があればコメントで指摘していただけると喜びます。
掛け算と割り算
よくある誤解として、コンピューターの掛け算は足し算をループして実装していると思われがちですが、そんなことはありません。
値は全て2進数で扱われるので足し算であれば
0100+0100=1000=8
みたいに一つずつ足しながらやるかと言えば、こんなクソコーダーみたいな実装はしないのです。
よく見ると、4の2進数
もう一つの例として
1000+1000+1000+1000=00100000=32
となります。これも、8の2進数を
シフト演算とは?
シフト演算には論理シフトと算術シフトという2種類の演算が存在します。
論理シフト
論理シフトは上の演算でも利用していた通り、レジスタ上のビットを全て左、右へ移動する演算です。移動して空いた端のビットには0が入ります。
上で紹介したシフト演算はこの論理シフトの左シフトといい、左へ
算術シフト
算術シフトは論理シフトと違い、符号を考慮します。レジスタにおいて、左端のビットは1であれば負の数、0であれば正の数といった感じで符号を表します。その符号ビットだけは残したまま他の全てのビットを論理シフトと同じようにずらす演算が算術演算です。
論理シフトしてみよう
ここまで簡単にシフト演算を説明してきましたが、実際に論理シフトを使った計算をしてみましょう。算術シフトに関しては論理シフトと計算方法は近いので割愛します。
問題1
32ビットのレジスタに16進数A6E2が入っている。これを3ビット右に論理シフトした値を16進数で求めよ
問題のレジスタを2進数で表すと0000 0000 0000 0000 1010(←A) 0110(←6) 1110(←E) 0010(←2)
になります。ここから3ビット分右に論理シフト、つまり3個分全ての値を右にずらしてみましょう。シフト後の値は0000 0000 0000 0000 0001 0100 1101 1100
、これを16進数に直すと、
よって答えは14DCになります。
問題2
レジスタに格納されている正の整数xを10倍にする処理を以下から選べ。この時桁が溢れることはない。
1. xを2ビット左にシフトした値にxを加算し、更に1ビット左にシフトする
2. xを2ビット左にシフトした値にxを加算し、更に2ビット左にシフトする
3. xを3ビット左にシフトした値と、xを2ビット左にシフトした値を加算する
4. xを3ビット左にシフトした値にxを加算し、更に1ビット左にシフトする
桁が溢れるというのはシフト演算の過程で1のビットが端から漏れるということです。
先述のシフト演算に関する前提知識があれば、式を作って計算してみれば簡単に答えがわかります。
選択肢1
xを2ビット左にシフトするということはつまり値は
ご覧の通り10倍になっているので選択肢1が正解です。試験などで解いた時はこれで次の問題に移って問題ないのですが一応他の選択肢も計算しておきましょう。
選択肢2
選択肢3
選択肢4
問題3
以下の16ビットの固定小数点レジスタの内容を3ビット論理左シフトしたものをa、2ビット論理右シフトしたものをbとした時、aがbの何倍になるのか求めよ。
0000 0100 1011 1000
3ビット論理左シフトした0010 0101 1100 0000
、2ビット論理右シフトした0000 0001 0010 1110
となります。この問題では桁溢れが起きないため、単純に
よって
おまけ-足し算と引き算
コンピューターの足し算は論理演算子を組み合わせて実現します。具体的には以下のような論理回路で計算を行います。
足し算であれば何不自由なく計算できるコンピューターですが、引き算は少し複雑です。繰り下がりに該当する論理回路が存在しないため足し算のような回路を組むことができないのです。ではどう引き算を実現しているのかというと、補数という値を利用します。
補数とは「任意の数
補数を使って引き算する
足し算を使って引き算、と言われると違和感しかありませんが補数を使った計算は至って簡単です。例として
9+4=13
この13の1の位に注目すると、3...なんと元々の引き算と同じ答えが出ているのです。被減数と補数を足して最上位の桁を取り除く、この方法でコンピューターは引き算をしています。感動
あれ、でも補数ってどうやって導くの?
賢い方は気づいたはず、上記の方法で引き算をしようとしても、そもそも補数を求めるのに引き算使ってるから意味ないじゃん、と。なんとなくブートストラップ問題的な、鶏卵な問題になりそうですが、実は2進数を機械的に扱うことで解決してしまうんです。
まず補数を算出する対象
1001は10進数に直すと12になり、本来4の補数は6であるべきなので間違いのように思えますが、この6は2の補数と言い、2進数で計算する上で
最上位の桁を無視すると
終わりに
僕はC言語やJavaを書いたことがないので実際にシフト演算をコードで実装したことはありませんが、いつの日か低レイヤーの鬼になってレジスタの実装とかしてみたいですね。
Discussion