颠倒二进制位

试题来源：力扣（英文），力扣（中文）

颠倒给定的 32 位无符号整数的二进制位。

Input:n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)

问题分析：

颠倒二进制位，一种常见的方式就是逐个读取每一位上的值，放到一个变量 res 中，即可完成颠倒，如下图所示。

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res <<= 1;// 往左移一位
        res += n & 1;// 取数字 n 的二进制中最右边的数字
//            res |= n & 1;// 取数字 n 的二进制中最右边的数字
        n >>>= 1;// 无符号右移
    }
    return res;
}

解法二

还一种方式就是把 int 类型的 32 位分成两部分，前后两部分交换，然后每部分在继续分两部分，各部分在继续交换……

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 16);// 前 16 位和后 16 位交换。
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);// 16 位一组，每组前 8 位和后 8 位交换。
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);// 8 位一组，每组前 4 位和后 4 位交换。
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);// 8 位一组，每组前 4 位和后 4 位交换。
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);// 2 位一组，每组前 1 位和后 1 位交换。
    return n;
}

对应的二进制如下

0xff00ff00 的二进制：11111111 00000000 11111111 00000000 
0x00ff00ff 的二进制：00000000 11111111 00000000 11111111 
0xf0f0f0f0 的二进制：11110000 11110000 11110000 11110000 
0x0f0f0f0f 的二进制：00001111 00001111 00001111 00001111 
0xcccccccc 的二进制：11001100 11001100 11001100 11001100 
0x33333333 的二进制：00110011 00110011 00110011 00110011 
0xaaaaaaaa 的二进制：10101010 10101010 10101010 10101010 
0x55555555 的二进制：01010101 01010101 01010101 01010101 

解法三

在 java 的 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 

最后是把 32 位二进制分成 4 份，1,4之间交换，2,3之间交换。