問題:
寫一個函數(shù) unsigned RevBit(unsigned val);
unsigned x = RevBit(0xf0ec9999);
x應(yīng)該為 0x9999370f。
0xf0ec9999 == 11110000111011001001100110011001(二進(jìn)制)
0x9999370f == 10011001100110010011011100001111（二進(jìn)制)思路：相鄰兩位互調(diào)位置（即一位換一位），再相鄰的兩位換兩位，在相鄰的四位與四位互調(diào)位置，再八位與八位互調(diào)位置，最后前十六位和后十六位互換位置，完成32位整數(shù)逆轉(zhuǎn)。思路與歸并排序相似。
代碼:
#include <stdio.h>;
unsigned RevBit(unsigned x)
{
x=(x&0x55555555)<<1|(x>>1)&0x55555555;
x=(x&0x33333333)<<2|(x>>2)&0x33333333;
x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;
x=(x&0x00ff00ff)<<8|(x>>8)&0x00ff00ff;
x=x<<16|x>>16;
return x;
}
int main()
{
unsigned x = RevBit(0xf0ec9999);
printf("%x\n",x);
return 0;
}
更多解法:
http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious