ビットシフトと高速化

ビットシフトって？

ずばり、桁を動かす演算方法です。
10進数で言えば10倍するという形です。(123x10→1230)


これをビット単位で行います。(演算子は<<です)
(10101)2　<< 2 →　(1010100)2


この動作を左に２ビットシフトすると言います。（後ろから０を２つ押し込むイメージ）

ビットシフトするとどうなるの？

2進数10進数に変換するときのイメージを考えてみると分かりやすいです。
(10101)2の場合は (1*2^4) + (0*2^3) + (1*2^2) + (0*2^1) + (1*2^0) = 21


ここで左に1ビットシフトさせてみましょう。

(101010)2 = (1*2^5) + (0*2^4) + (1*2^3) + (0*2^2) + (1*2^1) + (0*2^0) = 42
          =((1*2^4) + (0*2^3) + (1*2^2) + (0*2^1) + (1*2^0)) * 2      = (21)*2

このように2倍になります。
ｎ進数の場合、1ビット左にシフトするとｎ倍されるのです。
（10進数の場合、1桁あがると10倍だよね）

ビットシフトのお得感

普通に掛け算すればいいのでは？と疑問に思うかもしれません。
でも、実は掛け算というのは非常に重たい処理方法なのです。


例えば、7*3=7+7+7のように実装したり、複雑な回路を利用して実装したりと大変です。




そこで登場するのが論理演算のビットシフトです。
7*9を想定してみましょう。（7を9回足すと重いですよ）

7を8倍する　→　左に3ビットシフトする。(2^3=8) →　7<<3 = 56
残りを足す　→　７を足す　→　56 + 7 = 63

こんな感じに非常に速く演算することができます。
（DirectXなんかでテクスチャが2の倍数なのはこういうのが関係するらしい）




実際にはビットを横に動かすだけなので非常に高速な演算方法で

高速 ← 論理演算 ＞　加減算　＞＞＞　乗除算　→　低速 

ビットシフトは論理演算の部類に入り、ANDやORと同じ種類に分類されます。

シフト方法

論理シフト

普通にビットをシフトするだけです。
例え先頭ビットが符号ビットだろうとシフトします。
よって符号なしのデータに適しています。
(あふれた桁は無視されます)

算術シフト

符号のことをちゃんと考えてくれるシフト方法です。
符号ありのデータに適しています。
（あふれた桁は無視されます）

ローテート

循環シフトで、右側があふれた場合は左側に出現します。
(1001)2 << 1 = (0011)
ビット列が失われたくないとき、シーザー暗号等に向いていると思われます。






いかがでしたでしょうか、プログラミングの高速化手法としては定番でして試験等にも頻出です。
（例：MをNビット左にシフトして、その数にMを加えると何倍になるか）