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