【AP】論理シフト・算術シフト

基本的な知識を復習しつつAP対策するシリーズ。
この記事では論理シフト・算術シフトについてまとめます。

今、2進数01000100（10進数で68）について考えます。
この各ビットを左右に移動させて空いたビットを0で埋めることを論理シフトと言います。

f:id:halya_11:20190504211607p:plain:w300

上図のように左に論理シフトをすると値が2倍になります。
上図では01000100 (2進数) = 68 (10進数)を左に論理シフトして10001000 (2進数) = 136 (10進数)になっています。

前述のように左にシフトすると値が2倍になるのですが、その際に1があふれてしまうと値は2倍になりません。

f:id:halya_11:20190504211701p:plain:w300

10001000 (2進数) = 136 (10進数)を左に論理シフトして00010000 (2進数) = 16 (10進数)になっています。
これをオーバーフローと言います。

ちなみに右にシフトした場合にはオーバーフローは起こりません。

さて一番左のビットが符号を表す場合には、符号をシフトしてしまっては困ります。
そのため、一番左のビットを除いた部分だけをビットシフトします。

f:id:halya_11:20190504212506p:plain

これを算術シフトといいます。

論理シフトの節で書いたように、左にシフトをすると値が2倍になります。
この性質を利用して乗算をすることができます。

例えば元の値Aを3倍したい場合には、

${ \displaystyle A \times 3 = A \times 2^{1} + A \times 2^{0} }$

なので、左に1ビットシフトしたものと左に0ビットシフトしたものを加算すればOKです。