シフト演算って何に使う？(2)

前回に引き続き、シフト演算について。

今回は、その活用法についてです。

シフト演算を使うことで簡単に実装できる例題を2つ取り上げます。

まず、シフト演算は、数値を2進数と考えて処理をしているということから、2進数に関連する演算に使えそうです。ということで、『シフト演算を用いた10進・2進数変換』を紹介します。

いろいろなサイトに10進数を2進数にしたり、その逆をやったりする場合のコードがありますが、どれも・・・・な感じです。(イケてないです。。)

まあ普通にやるなら、

10進数 -> 2進数変換は、再帰を使ってやります。

2進数 -> 10進数変換は、Hormerの公式を使ってやるでしょう。

今回は、シフト演算を使って実装します。

こんなかんじ。

const int B_SIZE = 32;
char bin[B_SIZE + 1];

void ToBase2(int n, char *bin) {
REP(i, B_SIZE)
bin[B_SIZE - 1 - i] = (n >> i & 1) + '0';
bin[B_SIZE] = '\0';
}
int ToBase10(char *bin) {
int ret = 0;
REP(i, B_SIZE)
ret += bin[i] - '0' << B_SIZE - 1 - i;
return ret;
}

すごいシンプルです。気を付けないといけない点は、シフト演算の優先順位です。+, -よりも優先度が低いということに注意して下さい。

そして、2つ目はべき乗の計算。

シフトが何故べき乗に関係あるのか・・・。ちょっと説明します。

簡単な例として、3^128 を計算してみましょう。

3 * 3 * 3* .... (128回掛算して) ... * 3

なんてやってたらダメです。

3^128 = (3^64)^2 = ((3^32)^2)^2 = ....と分解して行けば、n乗の計算量はO(log(n))まで縮みます。

今回は、128（2の累乗）という数字だったので簡単でしたが、例えば、3^11なんてのはどうしましょう？

3^11 = 3^(8+2+1)と考えましょう。指数部分を2進数に分解しているようなイメージです。そして、逐次2乗を計算していき、2進数の桁数が1の場合は、答えに積算といった感じです。

『百聞は一見に如かず』ということでコードをどうぞ。

double powerSht(double x, int n) {
double ret = 1.0;
double tmp = x;

REP(i, 32) {
if (n >> i & 1)
ret *= tmp;
tmp *= tmp;
}
return ret;
}

実際に普通にn回掛け算する場合と速度を比較しましたが、1.000001^10000000を計算した場合、

約2000倍ほど差がでました。