005 按位反转字符问题

最后更新于:2022-04-01 14:40:14

## 【我解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 的相关介绍。
';