按位反轉(zhuǎn)字符問題

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.

方法一：（最最容易想到的辦法）

unsigned char ReverseBitsInChar00(unsigned char Num)

{

    unsigned char ret = 0;

    int i;

    for(i=0;i<8;i++)

    {

       ret <<= 1;

       ret |= Num & 1;

       Num >>=  1;

    }

    return ret;

}

上面的程序通過每次取傳入?yún)?shù)的最后一位( Num & 1)，然后與要返回的結(jié)果相 “ 或 ”，把傳入?yún)?shù) Num 右移 1 位，要返回的結(jié)果左移一位，來實(shí)現(xiàn)數(shù)字反轉(zhuǎn)的。

 方法二：  （對(duì)換）

unsigned char ReverseBitsInChar01(unsigned char Num)

{

    unsigned char 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;

}

上面的程序通過對(duì)換來實(shí)現(xiàn)的。

1、先找到低位，然后移動(dòng)到對(duì)應(yīng)的高位，再與要返回的結(jié)果 或 。

2、再找到高位，然后移動(dòng)到對(duì)應(yīng)的低位，再與要返回的結(jié)果 或。

3、循環(huán)，直至對(duì)換 4 次。

方法三：   （分而治之）

unsigned char ReverseBitsInChar02(unsigned char 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 )。把反轉(zhuǎn)32

位的程序分別分解為反轉(zhuǎn) 2 位、4 位來實(shí)現(xiàn)的。無論是對(duì)于要反轉(zhuǎn)幾位，他們的算法是類似的。

1、取低位，左移。

2、右移，取高位。

3、（ 1、2 的結(jié)果） 或

方法四：   （分而治之）

unsigned char ReverseBitsInChar03(unsigned char Num)

{

    Num = (Num & 0x55) <<  1 | (Num & 0xAA) >>  1;

    Num = (Num & 0x33) <<  2 | (Num & 0xCC) >>  2;

    Num = (Num & 0x0F) <<  4 | (Num & 0xF0) >>  4;

    return Num;

}

這個(gè)程序采用的也是分而治之的策略( divide and conquer strategy )。把反轉(zhuǎn)32

位的程序分別分解為反轉(zhuǎn) 2 位、4 位來實(shí)現(xiàn)的。無論是對(duì)于要反轉(zhuǎn)幾位，他們的算法是類似的。

1、取低位，左移。

2、取高位，右移。

3、（ 1、2 的結(jié)果） 或

上面的四個(gè)程序，前兩個(gè)是我寫的，是一個(gè)按照常規(guī)思維方式寫的代碼。后面的兩個(gè)來自于 Henry S.Warren 的 《Hacker's Delight》一書中的有關(guān) Reversing Bits 的相關(guān)介紹。