Bit Reverse

main.cpp

#include <cstdio>
#include <cstdlib>
#include <vector>

#include <sys/time.h>
#include <algorithm>
#include <numeric>
 
double get_time_now()
{
  struct timeval time_now;
  gettimeofday(&time_now, NULL);
  return ( 1e-6 * time_now.tv_usec + time_now.tv_sec );
}


 
// // // // http://qnighy.hatenablog.com/entry/20091006/1254832950 
unsigned int bitreverse_bitops(unsigned int x) {
    x = (x & 0x55555555)<<1 | (x & 0xaaaaaaaa)>>1;
    x = (x & 0x33333333)<<2 | (x & 0xcccccccc)>>2;
    x = (x & 0x0f0f0f0f)<<4 | (x & 0xf0f0f0f0)>>4;
    x = (x & 0x00ff00ff)<<8 | (x & 0xff00ff00)>>8;
    x = (x & 0x0000ffff)<<16 | (x & 0xffff0000)>>16;
    return x;
}
unsigned int bitreverse_bitops_range(unsigned int x, unsigned int s){
  return bitreverse_bitops((x))>>(32-(s));
}


unsigned int bitreverse_uchar_bitops(unsigned int x) {
  return bitreverse_bitops((x))>>(32-(8));
}

unsigned char bitreverse_uchar_array(unsigned char x) {
  const static unsigned char ret[] = { 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 };
  return ret[x];
}

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

unsigned char bitreverse_uchar(unsigned char x) {
  // return bitreverse_uchar_bitops(x);
  return bitreverse_uchar_array(x);
  // return bitreverse_uchar_switch(x);
}

template<typename INT, size_t size>
struct bitreverse_impl {
  enum ENUMHACK {
    bit_length = size*8,
    bit_length_half = size*4,
    half_mask = (1<<bit_length_half)-1,
    size_half = size>>1,
  };
  static int apply(const INT input) {
    return
      ( bitreverse_impl<INT, size_half>::apply(input>>bit_length_half) ) 
      | ( bitreverse_impl<INT, size_half>::apply(input) <<bit_length_half );
  };
};

template<typename INT>
struct bitreverse_impl<INT, 1> {
  static int apply(const INT input) {
    return bitreverse_uchar(input&255);
  };
};
 
 
 
 
template<typename INT>
INT bitreverse(const INT input) {
  return bitreverse_impl<INT, sizeof(INT)>::apply(input);
}
 

int main()
{
  srand(3459879);
  const size_t num = 1<<15;
  std::vector<unsigned int> indata(num);
  std::vector<unsigned int> outdata(num);
  for(int i=0; i<num; ++i) {
    indata[i] = rand();
  }
  const double time_begin = get_time_now();
  for(int i=0; i<num; ++i) {
    outdata[i] = bitreverse(indata[i]);
    // outdata[i] = bitreverse_bitops(indata[i]);
  }
  const double time_end = get_time_now();

  
  for(int i=0; i<num; ++i) {
    fprintf(stderr, "%u %u\n", indata[i], outdata[i]);
  }

  const double mops = 1e-6 * num / ( time_end - time_begin );
  fprintf(stdout, "%g\n", mops);
  
  return 0;
}

int main1()
{
  typedef unsigned char uchar;
  const size_t size = sizeof(uchar)*8;
  for(int i=0; i<(1<<size); ++i) {
    int _i = bitreverse_uchar(i);
    fprintf(stdout, "case %d: return %d; ", i, _i);
  }
  return 0;
}

int main2()
{
  typedef unsigned char uchar;
  const size_t size = sizeof(uchar)*8;
  for(int i=0; i<(1<<size); ++i) {
    int _i = bitreverse_uchar(i);
    fprintf(stdout, "%d, ", _i);
  }
  return 0;
}