ビット逆転アルゴリズムのテンプレート化と最適化について

ビット逆転のアルゴリズムとして、効率的なコードとして、
以下のようなものがよく見られるようです。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
unsigned int v;
v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);
v = ((v & 0xcccccccc) >> 2) | ((v & 0x33333333) << 2);
v = ((v & 0xf0f0f0f0) >> 4) | ((v & 0x0f0f0f0f) << 4);
v = ((v & 0xff00ff00) >> 8) | ((v & 0x00ff00ff) << 8);
v = (v >> 16) | (v << 16);
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1bit単位、2bit単位、4bit単位、8bit単位で交換し、最後に16bit単位で交換した結果、ビットの並びが上下逆となります。
簡単に8bitでトレースしてみると、、

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
v == 01111001
　　↓　　左側　((01111001 & 10101010) >> 1)  => 00010100
　　↓　　右側　((01111001 & 01010101) << 1)  => 10100010
　　↓　　00010100 | 10100010
v == 10110110
　　↓　　左側　((10110110 & 11001100) >> 2)  => 00100001
　　↓　　右側　((10110110 & 00110011) << 2)  => 11001000
　　↓　　00100001 | 11001000
v == 11101001
　　↓　　左側　(11101001 >> 4)  => 00001110
　　↓　　右側　(11101001 << 4)  => 10010000
　　↓　　00001110 | 10010000
v == 10011110
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

という感じです。
書きだしてみると少し長くなりましたが、
頭で考えたほうがかえって分かりやすいアルゴリズムだと思います。
上記のアルゴリズムを見つけたときは感心しました。

因みに最初に自作したのは以下のようなものでした。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 自作初期型
T val = 0x89ABCDEF;

const T size = sizeof(T) * 8 - 1;
T tmp = 0;
for(T i = 0; i <= size; i++) {
 tmp |= (val & (1 << size)) >> (size - i);
 val <<= 1;
}
return tmp;
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

常にvalのMSBを取り出し、
tmpのLSBからMSBへ順番に型のサイズ分だけ繰り返して設定する事で逆転させています。
sizeofによって可変サイズに対応できるため、template可能です。
この場合のsizeofは、通常コンパイル時には最適化によって定数へと置き換えられ、
例えばunsigned short(以下 U16)の時、実質的なコードは、

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// コンパイラ最適化後イメージ
U16 val = 0xABCD;
// const T size = sizeof(T) * 8 - 1; <=削除される
U16 tmp = 0;
for(U16 i = 0; i <= 15; i++) {
 tmp |= (val & 0x8000) >> (15 - i);
 val <<= 1;
}
return tmp;
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

と、言った感じになります。


しかしながら、
汎用的ではあるものの、冒頭のアルゴリズムを目にして、
うがががが(；´Д｀)。。
となったため、
なんとか冒頭のアルゴリズムをtemplateに適用したいと考えました。

・・・
で、出来たのは以下のコード。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
template<typename t> static T reverseBits(T v) {
 assert(sizeof T <= 4);
 switch(sizeof T) {
  case 4: v = (v >> 16) | (v << 16);
  case 2: v = ((v & 0xff00ff00) >> 8) | ((v & 0x00ff00ff) << 8);
  case 1: v = ((v & 0xf0f0f0f0) >> 4) | ((v & 0x0f0f0f0f) << 4);
   v = ((v & 0xcccccccc) >> 2) | ((v & 0x33333333) << 2);
   v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);
 }
 return v;
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

switch文が入りました。

冒頭のアルゴリズムの特性として、
各行の交換式は干渉していないということが挙げられます。
なので、順番がどうであれ、最後には交換が出来るはずです。

ということなので、

交換順を逆に定義した上で、
switch文を全て通り抜けるようにしてやることで、必要な分だけ演算を実施させます。


が、このswitch文は入っているように見えるだけで、実際には入らないです。

これは関数テンプレートであり、渡される型はコンパイル時には決まっており、
また、switchの対象が型サイズであるために、これもコンパイル時に解決され、
つまり最初からジャンプ先が決定しているのでswitchする必要がなく、
コンパイラの最適化により、型サイズによって直接的に必要な交換式のみを実行するコードが生成されます。

また、別の問題として考えられるのは、
上記の交換式はすべて32bitのリテラルが組み込まれていることです。
『v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);』
これはキャストが発生するのでは？と懸念が出なくもないですが、
これもよほど頭の悪いコンパイラでない限り、outする型に合わせたコードを生成します。
それに、心配であれば以下のようにしてしまえば確実です。
『v = ((v & static_cast<T>(0xaaaaaaaa)) >> 1) | ((v & static_cast<T>(0x55555555)) << 1);』
これも結局コンパイル時に型が決定するので正しいリテラルになりますね。

というわけで、
仮に各サイズでこの関数テンプレートが実体化された時の最適化後のコードのイメージは、以下のようになります。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【v == 32bit】
U32 reverseBits(U32 v) {
 v = (v >> 16) | (v << 16);
 v = ((v & 0xff00ff00) >> 8) | ((v & 0x00ff00ff) << 8);
 v = ((v & 0xf0f0f0f0) >> 4) | ((v & 0x0f0f0f0f) << 4);
 v = ((v & 0xcccccccc) >> 2) | ((v & 0x33333333) << 2);
 v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);
 return v;
}
【v == 16bit】
U16 reverseBits(U16 v) {
 v = ((v & 0xff00) >> 8) | ((v & 0x00ff) << 8);
 v = ((v & 0xf0f0) >> 4) | ((v & 0x0f0f) << 4);
 v = ((v & 0xcccc) >> 2) | ((v & 0x3333) << 2);
 v = ((v & 0xaaaa) >> 1) | ((v & 0x5555) << 1);
 return v;
}
【v == 8bit】
U8 reverseBits(U8 v) {
 v = ((v & 0xf0) >> 4) | ((v & 0x0f) << 4);
 v = ((v & 0xcc) >> 2) | ((v & 0x33) << 2);
 v = ((v & 0xaa) >> 1) | ((v & 0x55) << 1);
 return v;
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

2012/10/13 細かな加筆修正（内容は変更なし）