题目信息

题目地址：https://leetcode-cn.com/problems/reverse-bits/

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

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

1
2
3
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

1
2
3
输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：
输入是一个长度为 32 的二进制字符串

题解一：挨个移位

首先嘛肯定是要想出通过某种组合位运算的方式来达到目的，通过位运算是直接操作的这个数字在当前语言的二进制串，否则通过循环模拟二进制串对于Java还要分正负最终还转成数字过程就有点笨重了。

怎么组合位运算达到反转目的呢？草稿纸上试一试

1
2
3
4
5
6
7
8
9
10
11
// 模拟一个长度为5的二进制串怎么反转
10011
// 取个位移到最高位
10011 & 1 << 4 = 10000
// ...
1001 & 1 << 3 = 1000
100 & 1 << 2 = 0
10 & 1 << 1 = 0
1 & 1 << 0 = 1

result = 10000 | 1000 | 1 = 11001

虽然好像没有一次计算解决问题的方式，但可以通过与运算、位移运算进行取值再移到反转之后的位置，通过循环挨个挨个的反转。最终通过或运算合到一起.

注意是或运算变成搞成求和了

1
2
3
4
5
6
7
8
public int reverseBits(int n) {
    int result = 0;
    for(int i=31; i >= 0; i--){
        result |= n & 1 << i;
        n = n >>> 1;
    }
    return result;
}

这题时间复杂度和空间复杂度就不谈了都是有限的常量,如果二进制串长度假设无限的可以设定为n，时间复杂度就是n，不过这里有优化的余地

1
for(int i=31; i >= 0 && n ！= 0; i--)

。加上n != 0 的条件，固定的32位数字可能实际只有几位，高位之后全都是补0的就没必要管了。

题解二：分治法

分治将大问题递归划分成小问题，通过解决小问题最终解决大问题的思想

将32位二进制串反转，可划分为将前16位反转和将后16位反转然后调换两个16位，其中前后16位怎么反转，也可划分为前8和后8位。…..最终划分到两个数的反转。

问题划分：

解决问题：


动图偷懒一点，主要是表示如下过程：

1
2
3
4
5
6
7
1 2 3 4 5 6 7 8
->
21 43 65 87
->
4321 8765
->
87654321

正常来说需要递归函数传入一组内容，函数进行拆分两组然后分别调用自身之后进行拼接。直到最后传入的是一位数，直接返回。

在这里由于整数的范围二进制串的长度是32，因此不需要去递归探底判断什么时候结束。我们直接知道有5层log2(32) = 5。直接按照从底求解的顺序写5步操作即可

先看第一个目标就是把相邻的两两的数反转。怎么通过整数的位运算让它的值的二进制发生这个变化呢？

打个草稿：

1
2
3
4
原数：10101101
偶位：1 1 1 0
奇位： 0 0 1 1
希望：01011110

懂了，取到奇位与偶位的两组数其他位补0,两组一个左移一个右移之后进行或运算达到目的

怎么取到奇位和偶位就很简单了，分别和10101010、01010101这种进行与运算自然就把其他位清零把奇偶位保持它们自己。

1
2
10101101 & 10101010 = 10101000
101011 & 010101 = 00000101

第一步反转：

1
(n & 101010 >> 1) | (n & 010101 << 1)

后面第二步第三步…都差不多了

1
2
(n & 11001100 >> 2) | (n & 00110011 << 2)
(n & 11110000 >> 4) | (n & 00001111 << 4)

那对于我们32位的整数来说也是一样了，开始编码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
	  // 用16进制写得短一点😂
    int g1 = 0x55555555; // 01010101010101010101010101010101
    int g2 = 0x33333333; // 00110011001100110011001100110011
    int g4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    int g8 = 0x00ff00ff; // 00000000111111110000000011111111
    int g16 = 0x0000ffff; //00000000000000001111111111111111 
    
    public int reverseBits(int n) {
        n = (n & ~g1) >>> 1 | (n & g1) << 1;
        n = (n & ~g2) >>> 2 | (n & g2) << 2;
        n = (n & ~g4) >>> 4 | (n & g4) << 4;
        n = (n & ~g8) >>> 8 | (n & g8) << 8;
        n = (n & ~g16) >>> 16 | (n & g16) << 16;
        return n;
    }
}

两个解法效率差不多因为范围限制在32,一个计算次数小于等于32一个计算次数是log2(32)=5.

总结

题解一还是容易就顺下去就写成了，分治法的也是容易想得到，其实我们在写早期关于字符串反转这些的时候大致的思想都用过，挨个移位还有分治。在这里只是细节不一样从直接操作元素到用运算达到相同效果。在分治编码的时候有两个注意点一个是位移运算的优先级是最高的因此在代码前分析的时候(n & 101010 >> 1) | (n & 010101 << 1)这样写是有问题的应该是(n & 101010) >> 1 | (n & 010101) << 1 这样才保证先与运算再位移最后进行或运算。第二个就是右位移按照推理逻辑是左边补0，如果写成>>当值为负数时补的是1就不属于推理的思路了。解题感受还不错。