この記事はSGGのアドベントカレンダー24日目、イブの記事です。去年の計算では今頃彼女ができて都心で遊んでいるはずだったのですが、なぜかパソコンの前に座っています。無念。
この記事ではコンピュータの掛け算と割り算に使われるシフト演算の説明と計算をします。筆者が勉強していて「すげー」と思った部分を書いているので間違っている点があればコメントで指摘していただけると喜びます。
掛け算と割り算
よくある誤解として、コンピューターの掛け算は足し算をループして実装していると思われがちですが、そんなことはありません。
値は全て2進数で扱われるので足し算であれば$0010+0010=0100$みたいな計算になるのですが、例えば$4\times2$の計算を
0100+0100=1000=8
みたいに一つずつ足しながらやるかと言えば、こんなクソコーダーみたいな実装はしないのです。
よく見ると、4の2進数$0100$と8の2進数$1000$だと、1の位置が1ビット左に移動してますね。このように、$n$ビット分移動した時に乗数が$2^n$になることをシフトといい、これを使った計算をシフト演算というのです。コンピューターはこのシフト演算を使って掛け算と割り算を計算しています。
もう一つの例として$8\times4$の計算をクソコーダー風にすると
1000+1000+1000+1000=00100000=32
となります。これも、8の2進数を$00001000$と考えると2ビット分移動しており、$2^2=4=乗数$が成り立っています。
シフト演算とは？
シフト演算には論理シフトと算術シフトという2種類の演算が存在します。
論理シフト
論理シフトは上の演算でも利用していた通り、レジスタ上のビットを全て左、右へ移動する演算です。移動して空いた端のビットには0が入ります。
上で紹介したシフト演算はこの論理シフトの左シフトといい、左へ$n$ビットシフトすると$2^n$倍されるという演算です。これを使って掛け算が行われています。割り算には右シフトといい、右へ$n$ビットシフトすると$2^{-2}$倍されるという演算が利用されています。
論理左シフト - Wikipedia
論理右シフト - Wikipedia
算術シフト
算術シフトは論理シフトと違い、符号を考慮します。レジスタにおいて、左端のビットは1であれば負の数、0であれば正の数といった感じで符号を表します。その符号ビットだけは残したまま他の全てのビットを論理シフトと同じようにずらす演算が算術演算です。
算術左シフト - Wikipedia
算術右シフト - Wikipedia
論理シフトしてみよう
ここまで簡単にシフト演算を説明してきましたが、実際に論理シフトを使った計算をしてみましょう。算術シフトに関しては論理シフトと計算方法は近いので割愛します。
問題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進数に直すと、
$0001=2^3\times0+2^2\times0+2^1\times0+2^0\times1=1$
$0100=2^3\times0+2^2\times1+2^1\times0+2^0\times0=4$
$1101=2^3\times1+2^2\times1+2^1\times0+2^0\times1=13=D$
$1100=2^3\times1+2^2\times1+2^1\times0+2^0\times0=12=C$
よって答えは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ビット左にシフトするということはつまり値は$2^2$倍されることになります。そしてその値にxを加算し($+x$)、更に1ビット左にシフトする、つまり$2^1$倍した結果を調べれば10倍かどうか分かるというわけです。
$x'=(x\times2^2+x)\times2^1=5x\times2=10x$
ご覧の通り10倍になっているので選択肢1が正解です。試験などで解いた時はこれで次の問題に移って問題ないのですが一応他の選択肢も計算しておきましょう。
選択肢2
$x'=(x\times2^2+x)\times2^2=5x\times4=20x$
選択肢3
$x'=x\times2^3+x\times2^2=8x+4x=12x$
選択肢4
$x'=(x\times2^3+x)\times2^1=9x\times2=18x$
問題3
以下の16ビットの固定小数点レジスタの内容を3ビット論理左シフトしたものをa、2ビット論理右シフトしたものをbとした時、aがbの何倍になるのか求めよ。
0000 0100 1011 1000
3ビット論理左シフトした$a$は0010 0101 1100 0000、2ビット論理右シフトした$b$は0000 0001 0010 1110となります。この問題では桁溢れが起きないため、単純に$a$は元のレジスタの内容から$2^3$倍値が増え、$b$は$2^{-2}$倍値が増えた物であると考えられるのです。この時比べたいのは$a$と$b$ですから、元のレジスタの内容を$x$とすると
$\frac{a}{b}=\frac{2^3x}{\frac{x}{2^2}}=\frac{2^3x\times2^2}{x}=2^5=32$
よって$a$は$b$の32倍という結果になる。
おまけ-足し算と引き算
コンピューターの足し算は論理演算子を組み合わせて実現します。具体的には以下のような論理回路で計算を行います。
加算器 - Wikipedia
足し算であれば何不自由なく計算できるコンピューターですが、引き算は少し複雑です。繰り下がりに該当する論理回路が存在しないため足し算のような回路を組むことができないのです。ではどう引き算を実現しているのかというと、補数という値を利用します。
補数とは「任意の数$n$に足せば繰り上がりする数」のことです。10進数で言えば$n+補数=10$の数値ということで、1の補数は9、7の補数は3といった具合に補数が決定します。
補数を使って引き算する
足し算を使って引き算、と言われると違和感しかありませんが補数を使った計算は至って簡単です。例として$9-6$の計算をしてみたいと思います。
$9-6$の計算において、補数を求める$n$は6になります(減数)。つまり補数は4になるのですが、ここで被減数(引かれる数)と補数を足してみましょう。
9+4=13
この13の1の位に注目すると、3...なんと元々の引き算と同じ答えが出ているのです。被減数と補数を足して最上位の桁を取り除く、この方法でコンピューターは引き算をしています。感動
あれ、でも補数ってどうやって導くの？
賢い方は気づいたはず、上記の方法で引き算をしようとしても、そもそも補数を求めるのに引き算使ってるから意味ないじゃん、と。なんとなくブートストラップ問題的な、鶏卵な問題になりそうですが、実は2進数を機械的に扱うことで解決してしまうんです。
まず補数を算出する対象$x$を4とします。この4を2進数で表すと0100となります。この2進数を反転させたビットに1を足すと、補数が求まってしますのです！計算して確かめてみましょう。
$1011+1=1100$
1001は10進数に直すと12になり、本来4の補数は6であるべきなので間違いのように思えますが、この6は2の補数と言い、2進数で計算する上で$x$と足しても繰り上がりをしない最大の数なのです。つまり今までこのおまけ章で扱ってきた補数は10進数用、10の補数だったというわけです。2の補数を10進数で使っても上手くいくはずがないので、被減数を8(=1000)として2進数で4の補数を足してみましょう。
$1000+1100=10100$
最上位の桁を無視すると$0100=4$、10進数で計算した$8-4=4$と一致し、足し算だけで引き算を実現することができました。
終わりに
僕はC言語やJavaを書いたことがないので実際にシフト演算をコードで実装したことはありませんが、いつの日か低レイヤーの鬼になってレジスタの実装とかしてみたいですね。僕が入っているSGGもメンバー募集中ですので興味のある学生の方はいつでも声かけてください。