位元反轉 (Reverse bits)

在程式中常常會用到位元反轉的運算，之前因為常常沒去理解原理，所以要用的時候沒辦法自己寫出來，既然不想花時間理解，那就抄下來吧~~~(太混)!!

參考底下連結
http://www-graphics.stanford.edu/~seander/bithacks.html#OperationCounting

好啦~方法太多那就從簡單的互換位置來理解一下吧。
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairsv = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);// swap nibbles ... v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);// swap bytesv = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);// swap 2-byte long pairsv = ( v >> 16             ) | ( v               << 16);

另外再把查表法跟乘法原則的方式也貼出來~
乘法原則：
((v*0x00208208 & 0x01020408) * 0x01010101) >> 24

查表法
static const unsigned char BitReverseTable256[256] = 
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

// Option 2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]];

The first method takes about 17 operations, and the second takes about 12, assuming your CPU can load and store bytes easily.