[数据结构与算法]LeetCode 190. 颠倒二进制位

截止到目前我已经写了 600多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

问题分析

这题是让把一个int类型的二进制位反过来，比如abcd，要把他变成dcba。最简单的一种方式就是通过一个循环，每次循环的时候把n的最后一位数字（二进制的）截取掉，放到一个新的数字中的末尾，可以看下视频
视频链接

原理比较简答，我们来看下代码

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        //res先往左移一位，把最后一个位置空出来，
        //用来存放n的最后一位数字
        res <<= 1;
        //res加上n的最后一位数字
        res |= n & 1;
        //n往右移一位，把最后一位数字去掉
        n >>= 1;
    }
    return res;
}

我们知道在java中int类型是32位的，我们还可以使用一个临时变量res，把

• n的二进制位中右边第1位放到res二进制位右边第32位，
• n的二进制位中右边第2位放到res二进制位右边第31位，
• n的二进制位中右边第3位放到res二进制位右边第30位，
• ……

这样最终也可以实现，原理比较简单，来看下代码

public int reverseBits(int n) {
    int res = 0;
    //把低16位移到高16上
    for (int i = 0; i < 16; i++) {
        res |= (n & (1 << i)) << (31 - i * 2);
    }
    //把高16位移到低16位上
    for (int i = 16; i < 32; i++) {
        res |= (n & (1 << i)) >>> (i * 2 - 31);
    }
    return res;
}

我们还可以不使用循环，就是前面16个和后面16个交换，然后前面16个和后面16个中的8个8个在交换……直到两两交换为止。

看下视频

代码如下

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 16);
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
    return n;
}

除了上面介绍的3种解法以外，还有一种解决方式就是每2位之间相互交换，然后是每4位之间相互交换，接着是每8位之间相互交换，但最后不是每16位之间交换，而是把32位分为4个8位，这4个8位之间相互交换，具体也可以看下

364，位1的个数系列（一）

385，位1的个数系列（二）

402，位1的个数系列（三）

来看下代码（经常看源码的同学会发现，这个就是源码Integer中的代码。）

public static int reverseBits(int var0) {
    var0 = (var0 & 1431655765) << 1 | var0 >>> 1 & 1431655765;
    var0 = (var0 & 858993459) << 2 | var0 >>> 2 & 858993459;
    var0 = (var0 & 252645135) << 4 | var0 >>> 4 & 252645135;
    var0 = var0 << 24 | (var0 & '\uff00') << 8 | var0 >>> 8 & '\uff00' | var0 >>> 24;
    return var0;
}

上面数字的二进制位如下：

1431655765的二进制是：01010101 01010101 01010101 01010101 
858993459 的二进制是：00110011 00110011 00110011 00110011 
252645135 的二进制是：00001111 00001111 00001111 00001111 
'\uff00'  的二进制是：00000000 00000000 11111111 00000000