基数と補数の計算

科目Aの計算は型で解く

ここからは科目Aに切り替えます。知識そのものはCSコースで扱った内容が土台になるので、この章では毎回のように出題される計算問題だけを、解き方の型として身に付けます。型さえ手が覚えていれば、本番では数字を差し替えるだけで答えが出ます。

最初は基数と補数です。出題は基数変換、負数の表現、シフト演算の 3 つに分かれます。

基数変換は位の重みに戻す

2 進数は各桁が 1、2、4、8、16 と重みを持ちます。10 進の 45 を 2 進にするなら、45 に収まる最大の重みから引いていきます。45 から 32 を引いて 13、13 から 8 を引いて 5、5 から 4 を引いて 1、最後に 1 を引いて 0 です。使った重みは 32、8、4、1 なので、6 桁で書くと 101101 になります。

2 進数を 16 進数にするときは、下の桁から 4 ビットずつ区切ります。101101 を区切ると 0010 と 1101 になり、それぞれ 2 と D なので 2D です。4 ビットが 16 進 1 桁にちょうど対応するので、割り算をする必要はありません。

小数も同じで、2 進の小数点以下は 0.5、0.25、0.125 という重みです。10 進の 0.1 はこの重みの和で表しきれないため無限に続きます。浮動小数点数の誤差が出る理由はここにあります。

2 の補数は「反転して 1 を足す」

コンピュータは引き算を足し算で行います。そのために負の数を 2 の補数という形で持ちます。作り方は 2 手です。

1. 絶対値を 2 進数で書き、全ビットを反転する
2. その結果に 1 を足す

8 ビットで -5 を表してみます。5 は 00000101 です。反転すると 11111010、1 を足して 11111011 になります。これが -5 です。

正しいかどうかは、元の 5 を足してみれば確かめられます。11111011 + 00000101 は 100000000 となり、8 ビットからあふれた 1 は捨てられるので 00000000、つまり 0 です。足して 0 になるのだから、確かに -5 の役割を果たしています。

最上位ビットが 1 なら負、0 なら正です。8 ビットの 2 の補数で表せる範囲は -128 から 127 で、負のほうが 1 つ多くなります。0 の表現が 1 つしかないためです。

シフトは掛け算と割り算

左へ 1 ビットずらすと値は 2 倍、右へ 1 ビットずらすと 2 分の 1 になります。3 ビット左にずらせば 8 倍です。

右シフトには 2 種類あります。空いた上位ビットに 0 を入れるのが論理シフト、元の符号ビットと同じ値を入れるのが算術シフトです。負数を 2 で割りたいときに論理シフトを使うと符号が壊れるため、符号付きの数には算術シフトを使います。

00011000 は 24 です。算術右シフトを 2 回行うと 00000110 になり、値は 6 です。24 を 4 で割った値と一致します。

この性質を使うと、掛け算をシフトと加算に分解できます。x に 10 を掛けたいなら、10 は 8 と 2 の和なので、x を 3 ビット左シフトした値と 1 ビット左シフトした値を足せば求まります。乗算命令より速いので、実装の工夫としても出題されます。