Feb 28, 2006
ビットシフトと高速な演算
2進数では、ビット列をずらすだけで簡単に2n倍または1/(2n)倍（できる。
| 10進数 | 2進数（ビット列） |
|---|---|
| 1 | 0000001 |
| 2 | 0000010 |
| 4 | 0000100 |
| 8 | 0001000 |
| 16 | 0010000 |
| 32 | 0100000 |
| 64 | 1000000 |
2進数というのは0と1というビットの並び（ビット列）でできている。数値を2倍するというのは、このビット列を1つ左にずらすことに等しく、1/2倍する（2で割る）というのは、1つ右にずらすことに等しい。
4倍するというのは、2×2倍すること＝2回2倍するということ。つまり、数値を4倍するというのは、このビット列を左に2つずらすということだ。
8倍するというのは、2×2×2倍すること＝3回2倍するということ。つまり、数値を8倍するというのは、このビット列を左に3つずらすということだ。
2進数が基本になっているコンピュータでは、2の倍数をかける（2の倍数で割る）計算はこのようにすれば、何の面倒もなく物凄く高速に結果を得ることができるわけである。ゲームプログラミングのようなとにかく高速なレスポンスが要求される分野では、こういうテクニックが多用されるのだそうだ。
……と、2進数が特別であるかのように書いてみたけれども、よく考えればべつに2進数だけに限ったことじゃあない。みんなも小学校の算数で覚えただろう。10倍すると、桁が1つ上がって末尾に0が増えるだけで済む。100倍（102倍）なら0が2つ増えるだけ。1000倍（103倍）なら3つ増えるだけ。10n倍する計算は楽でいい。ということを。
同様に、8進数は8倍すれば1桁上がり、8で割れば1桁下がる。16進数は16倍すれば1桁上がり、16で割れば1桁下がる。何進数でもこれは成り立つ。
一般化するとこういうことだ。n進数をnm倍すると、m桁上がる。nmで割ると、m桁下がる。
よっぽど効率が重視されるプログラミングの現場でもなければそんなに役に立たない知識なので、まあ、トリビアってことで。
wikieditish message: Ready to edit this entry.