## 【我解C語言面試題系列】005 按位反轉字符問題
**按位反轉字符問題**
Write a C function to swap the bits of a unsigned char so that its bits become the mirror image of the char. MSBs become its LSBs, e.g.? 01111000 binary should become 00011110 binary.
方法一：（最最容易想到的辦法）
~~~
unsignedchar ReverseBitsInChar00(unsignedchar Num)
{
?? unsignedchar ret = 0;
?? int i;
?? for(i=0;i<8;i++)
?? {
????? ret <<= 1;
????? ret |= Num & 1;
????? Num >>=? 1;
?? }
?? return ret;
}
~~~
上面的程序通過每次取傳入參數的最后一位( Num & 1)，然后與要返回的結果相 “ 或 ”，把傳入參數 Num 右移 1 位，要返回的結果左移一位，來實現數字反轉的。
方法二：? （對換）
~~~
unsignedchar ReverseBitsInChar01(unsignedchar Num)
{
?? unsignedchar ret = 0;
?? int i;
?? for(i=0;i<4;i++)
?? {
??????? ret |= (Num & (1 << i)) << (7-2*i);
??????? ret |= (Num & (0x80 >> i) ) >> (7-2*i);
?? }
?? return ret;
}
~~~
上面的程序通過對換來實現的。
1、先找到低位，然后移動到對應的高位，再與要返回的結果 或 。
2、再找到高位，然后移動到對應的低位，再與要返回的結果 或。
3、循環，直至對換 4 次。
方法三：?? （分而治之）
~~~
unsignedchar ReverseBitsInChar02(unsignedchar Num)
{
?? Num = (Num & 0x55) <<? 1? | (Num >>? 1) & 0x55;
?? Num = (Num & 0x33) <<? 2? | (Num >>? 2) & 0x33;
?? Num = (Num & 0x0F0F) <<? 4? | (Num >>? 4) & 0x0F0F;
?? return Num;
}
~~~
上面的程序采用的是分而治之的策略( divide and conquer strategy )。把反轉32
位的程序分別分解為反轉 2 位、4 位來實現的。無論是對于要反轉幾位，他們的算法是類似的。
1、取低位，左移。
2、右移，取高位。
3、（ 1、2 的結果） 或
方法四：?? （分而治之）
~~~
unsignedchar ReverseBitsInChar03(unsignedchar Num)
{
?? Num = (Num & 0x55) <<? 1 | (Num & 0xAA) >>? 1;
?? Num = (Num & 0x33) <<? 2 | (Num & 0xCC) >>? 2;
?? Num = (Num & 0x0F) <<? 4 | (Num & 0xF0) >>? 4;
?? return Num;
}
~~~
這個程序采用的也是分而治之的策略( divide and conquer strategy )。把反轉32
位的程序分別分解為反轉 2 位、4 位來實現的。無論是對于要反轉幾位，他們的算法是類似的。
1、取低位，左移。
2、取高位，右移。
3、（ 1、2 的結果） 或
上面的四個程序，前兩個是我寫的，是一個按照常規思維方式寫的代碼。后面的兩個來自于 Henry S.Warren 的 《Hacker's Delight》一書中的有關 Reversing Bits 的相關介紹。
