分类： C/C++
2007-11-09 16:57:15
反转一个字节的算法
//算法1，查表法，典型的空间换时间，在现代的CPU上，这种算法具有最快的速度。
unsigned char reverse1(unsigned char c)
{
static unsigned char table[256] =
{
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF
};
return table[c];
}
//算法2，逆向移位，思路很简单，代码却有点长.
unsigned char reverse2( unsigned char c)
{
unsigned char r = 0;
//r <<= 0,c >>= 0;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
r <<= 1,c >>= 1;
r |= c&1;
return r;
}
//算法3，逆向移位，和上一个算法相同，但是用了循环，所以效率可能有点低。
unsigned char reverse3( unsigned char c)
{
unsigned char r = 0;
r |= c&1;
for( int i = 0; i < 7; i++)
r <<= 1,c >>= 1,r |= c&1;
return r;
}
//算法4，逐位判断，看起来似乎比算法2更简洁，但是因为if语句牵涉到一个跳转指令引起流水线重置的问题，在现在的CPU上不见得更快速。
unsigned char reverse4( unsigned char c)
{
unsigned char r = 0;
if( c&0x01 ) r |= 0x80;
if( c&0x02 ) r |= 0x40;
if( c&0x04 ) r |= 0x20;
if( c&0x08 ) r |= 0x10;
if( c&0x10 ) r |= 0x08;
if( c&0x20 ) r |= 0x04;
if( c&0x40 ) r |= 0x02;
if( c&0x80 ) r |= 0x01;
return r;
}
//算法5，分段查表法。查表法虽然快，但是表有256个字节大，有些时候可能显得太大了。
//表太大，书写不方便，而且看起来也比较凌乱。所以才有了下面的算法，只用16字节的表。
unsigned char reverse5( unsigned char c)
{
static unsigned char table[16] =
{
0x00,0x08,0x04,0x0C,0x02,0x0A,0x06,0x0E,0x01,0x09,0x05,0x0D,0x03,0x0B,0x07,0x0F
};
unsigned char r = 0;
r |= (table[c&0xF]) << 4;
r |= table[c>>4];
return r;
}
//效率测试代码：
#include
using namespace std;
typedef unsigned __int64 ULONGLONG;
inline ULONGLONG GetCycleCount()
{
__asm RDTSC
}
int main(int argc, char* argv[])
{
int i = 0,n = 10000;
int c = 0;
ULONGLONG t1 = GetCycleCount();
for( i = 0; i < n; i++)
c += reverse1(i);
ULONGLONG t2 = GetCycleCount();
for( i = 0; i < n; i++)
c += reverse2(i);
ULONGLONG t3 = GetCycleCount();
for( i = 0; i < n; i++)
c += reverse3(i);
ULONGLONG t4 = GetCycleCount();
for( i = 0; i < n; i++)
c += reverse4(i);
ULONGLONG t5 = GetCycleCount();
for( i = 0; i < n; i++)
c += reverse5(i);
ULONGLONG t6 = GetCycleCount();
cout << " T1 = " << int(t2-t1)/n
<< " T2 = " << int(t3-t2)/n
<< " T3 = " << int(t4-t3)/n
<< " T4 = " << int(t5-t4)/n
<< " T5 = " << int(t6-t5)/n
<< " \n C = " << c //输出c是为了避免编译器优化。
<< endl;
return 0;
}
//测试环境：
CPU:AMD2400+，超频至1.9G
内存：512M
VC6 sp5,win2kpro sp4
//测试结果:
T1 = 11 T2 = 27 T3 = 38 T4 = 34 T5 = 15
C = 6374400
Press any key to continue
最后，补充一点，除了两个查表算法外，其他算法都可以通过添加inline修饰成为内联，而使得执行效率不同程度的提升，但是即使这样，它们的效率也无法和两个查表算法相比。
第一种查表，在内存访问量比较大的时候，会频繁出现突发的效率降低，原因估计是整个表被置换出了CPU的cache，这时候算法5的优越性就体现出来了。
