ビットリバース

C++ utility

割合汎用的な、整数のビットを前後反転する関数を作成してみた。
2の乗数サイズの任意の整数型のビット反転が可能。

// 反転例
bit_reverse(0x0000FFFF) => 0xFFFF0000

// 実装

// バイト単位での変換表
const unsigned char REV_BYTE[]={
  0,128,64,192,32,160,96,224,16,144, 80,208,48,176,112,240,8,136,72,200,
  40,168,104,232,24,152,88,216,56,184,120,248,4,132,68,196,36,164,100,228,
  20,148,84,212,52,180,116,244,12,140,76,204,44,172,108,236,28,156,92,220,
  60,188,124,252,2,130,66,194,34,162,98,226,18,146,82,210,50,178,114,242,
  10,138,74,202,42,170,106,234,26,154,90,218,58,186,122,250,6,134,70,198,
  38,166,102,230,22,150,86,214,54,182,118,246,14,142,78,206,46,174,110,238,
  30,158,94,222,62,190,126,254,1,129,65,193,33,161,97,225,17,145,81,209,
  49,177,113,241,9,137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,
  5,133,69,197,37,165,101,229,21,149,85,213,53,181,117,245,13,141,77,205,
  45,173,109,237,29,157,93,221,61,189,125,253,3,131,67,195,35,163,99,227,
  19,147,83,211,51,179,115,243,11,139,75,203,43,171,107,235,27,155,91,219,
  59,187,123,251,7,135,71,199,39,167,103,231,23,151,87,215,55,183,119,247,
  15,143,79,207,47,175,111,239,31,159,95,223,63,191,127,255};

// リバースクラス
template <int BYTE_SIZE> 
struct bit_rev {
  static const int HALF_SIZE = BYTE_SIZE/2;
  static const int HALF_BITS = HALF_SIZE*8;
  
  // BYTE_SIZEが1以外なら、上位ビットと下位ビットに再帰的に処理を適用した後に、二つを入れ替える
  template <typename T>
  static T reverse(T n) {
    return 
      (bit_rev<HALF_SIZE>::reverse(n) << HALF_BITS) | 
      (bit_rev<HALF_SIZE>::reverse(n>>HALF_BITS));
  }  
};

// BYTE_SIZEが1ならテーブルを参照して、バイトを変換する
template <> struct bit_rev<1> {
  template <typename T>
  static T reverse(T n) {
    return REV_BYTE[n&0xFF];
  }
};

// インターフェース関数
template <typename T>
T bit_reverse(T n) {
  return bit_rev<sizeof(T)>::reverse(n);
}

サンプルコマンド:

/**
 * ファイル名: rev.cc
 * コンパイル: g++ -o rev rev.cc
 */
#include <iostream>

/*
 bit_reverse関数定義
 */

int main() {
  unsigned char n08 = 0x0F;
  unsigned short n16 = 0x009F;
  unsigned int n32 = 0x0000699F;
  unsigned long long n64 = 0x00000000666699FF;
  
  std::cout.setf(std::ios::hex, std::ios::basefield);
  std::cout.setf( std::ios::showbase );

  std::cout << "n08: " << (long long)n08 << " => " << (long long)bit_reverse(n08) << std::endl;
  std::cout << "n16: " << (long long)n16 << " => " << (long long)bit_reverse(n16) << std::endl;
  std::cout << "n32: " << (long long)n32 << " => " << (long long)bit_reverse(n32) << std::endl;
  std::cout << "n64: " << (long long)n64 << " => " << (long long)bit_reverse(n64) << std::endl;
  return 0;
}

実行結果:

$ ./rev
n08: 0xf => 0xf0
n16: 0x9f => 0xf900
n32: 0x699f => 0xf9960000
n64: 0x666699ff => 0xff99666600000000

自分の環境で軽く試した感じでは、ビット演算のみを使用して手書きで最適化したものと同等以上の速度が出ていた。