把一个32位的二进制进行逆序处理-xwjazjx1314-ChinaUnix博客

Also check http://massivealgorithms.blogspot.com/2014/06/reverse-integer-leetcode-easycpp.html
把一个32位的二进制进行逆序处理-xwjazjx1314-ChinaUnix博客

设想一下，逆序'ab',为'ba'。

逆序abcd，可以先两两交换为cdab，然后一一交换为dcba。

逆序abcdefgh，先四四交换efghabcd，然后两两交换fehgcdab，然后一一交换efghdcaba。

那么可以推广到二进制表示：

第一步：每2位为一组，组内高低位交换

       00 11 00 00 00 11 10 01

  -->00 11 00 00 00 11 01 10

第二步：每4位为一组，组内高低位交换

       0011 0000  0011 0110

  -->1100 0000 1100 1001

第三步：每8位为一组，组内高低位交换

       11000000 11001001

  -->00001100 10011100

第四步：每16位为一组，组内高低位交换

       0000110010011100

  -->1001110000001100

高低位互换时操作大概就是偶数位左移1位，奇数位右移1位

      原 数   00110000 00111001

      奇数位 0_1_0_0_ 0_1_1_0_

      偶数位 _0_1_0_0 _0_1_0_1

其余位数用0填充，然后将奇数位右移一位，偶数位左移一位，此时将这两个数据做按位与运算，即可以达到奇偶位上数据交换的效果了：

JDK code: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/Integer.java

    public static int reverse(int i) {
        // HD, Figure 7-1
        i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
        i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
        i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
        i = (i << 24) | ((i & 0xff00) << 8) |
            ((i >>> 8) & 0xff00) | (i >>> 24);
        return i;
    }

def reverseBinary(a):
    a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
    a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2) 
    a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4) 
    a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
    return a

1. int main() {
2.     int n;
3.     while (scanf("%d", &n) != EOF) {
4.         n = (n & 0x55555555) << 1 | (n & 0xAAAAAAAA) >> 1;
5.         n = (n & 0x33333333) << 2 | (n & 0xCCCCCCCC) >> 2;
6.         n = (n & 0x0F0F0F0F) << 4 | (n & 0xF0F0F0F0) >> 4;
7.         n = (n & 0x00FF00FF) << 8 | (n & 0xFF00FF00) >> 8;
8.         n = (n & 0x0000FFFF) << 16 | (n & 0xFFFF0000) >> 16;
9.         printf ("%d\n", n);
10.     }
11.     return 0;
12. }
13. 其实，这种方法很好理解，上面的意思就是通过移位，先两两交换。看下图就明白其中的原理了。
14. 假如一个8位的二进制数，就是如图所示：11 10 01 00 先1跟1交换，1跟0交换，0跟1交换 0跟0交换。
15. 第二步就是11 与01交换。。。最后，得出所需要的结果。 16位及32位类似。

                

     
这种方法的好处就是：直观明了，一步一步的往下执行。

最直接的方法

http://segmentfault.com/a/1190000003483740

最简单的做法，原数不断右移取出最低位，赋给新数的最低位后新数再不断左移。

    public int reverseBits(int n) {
        int res = 0;
        for(int i = 0; i < 32; i++, n >>= 1){
            res = res << 1 | (n & 1);
        }
        return res;
    }

http://www.faceye.net/search/111914.html

最容易想到的方法就是依次交换两端的数据，从右向左遍历数字，当i位遇到1时，将逆序数字对应的(17-i)位设为1。

def reverseBinary(num):
    print bin(num)
    new=0
    tmp=(1<<15)
    for i in xrange(16):
        if num&1:
            new|=tmp
        tmp>>=1
        num>>=1
    return new

Convert to char array ==> not good

void bitreverse(char *s, int x)

{

    int i = 0;

    for(; i < INTBIT; x >>= 1)

    {

        s[i++] = x & 1 ? '1' : '0';

    }

    s[i] = '\0';

}

1. int reverse( int n )
2. {
3.     unsigned int tmp;
4.     unsigned int maskl=0x01;
5.     unsigned int maskh=0x80000000;
6.     unsigned int rst=0;
7.     int i,j;
8.     for(i=0;i<15;i++)
9.     {
10.           tmp=n&maskl;
11.           maskl=maskl<<1;
12.           for(j=i+1;j<=31-i;j++)
13.                 tmp=tmp<<1;
14.           rst=tmp | rst;
15.     }
16.     for(i=0;i<15;i++)
17.     {
18.           tmp=n&maskh;
19.           maskl=maskh>>1;
20.           for(j=i+1;j<=31-i;j++)
21.                 tmp=tmp>>1;
22.           rst=tmp | rst;
23.     }
24.     return rst;
25. }

这种方法也是类似。先取出高位或者低位，再按位或。

Read full article from 把一个32位的二进制进行逆序处理-xwjazjx1314-ChinaUnix博客