190. Reverse Bits

题目

题意分析

本题是要将一个无符号32位整数的所有二级制位逆序，即110转换成011。

本题考点

二进制逆序

解法I - 循环相加实现逆序

二进制的逆序与十进制类似，我们可以直接使用十进制逆序的方法（参考: 7. Reverse Integer)实现。

二进制与十进制不同的地方有二：

一是十进制整数取最后一位的方法与二进制数取最后一位的方法不同：十进制为n % 10, 二进制为n & 1

二是十进制每次需要让整数缩小为原整数的十分之一以取出原整数倒数第二位，二进制需要每次缩小为原整数的二分之一来取出原倒数第二位

注意，本处不需要讨论正负性，只需逆序二进制即可。

实现

时间复杂度O(k)，空间复杂度O(1)，其中k为原整数二进制的位数, 本题k = 32

public class Solution {
  // you need treat n as an unsigned value
  public int reverseBits(int n) {
    int reversed = 0;

    for (int i = 0; i < 32; i++) {
      // 我们使用n & 1来获取二进制数的最后一位
      reversed = (reversed << 1) + (n & 1);
      n >>= 1;
    }

    return reversed;
  }
}

解法II - 分治

上面的算法已经做到了几乎是常数的时间复杂度，对于所有输入数据，32次循环从时间上来说可以忽略不计，我们能不能想想办法使得操作次数再少一点呢？

对于二进制，我们本能地需要想一想能否使用二分、分治等时间复杂度为logN的算法来实现。

对于逆序问题，我们首先应该想到的就是分治：

对于两位数ab, 逆序后的结果为ba;

对于四位数abcd, 我们把它看成ab与cd的两个两位数，首先将ab与cd逆序，得到cd ab, 再将两部分分别逆序, 得到dcba

同理，对于八位数abcdefgh, 操作流程为: abcd efgh => efgh abcd => ghef cdab => hgfe dcba

那么对于32位整数，我们可以分成16位的两部分，继而8位，4位依次，即可最终得到逆序后的结果。

我们有reverse(n) = reverse(n的左半部分) | reverse(n的右半部分）

有了以上理论基础后，我们来模拟三十二位二进制数整个逆序过程，设三十二位二进制数为n, 以题目中第一个测试数据0000001010010100 0001111010011100为例。

1. 以16位为一组，两两互相交换顺序:

   n = ((n & 0xffffffff) >> 16) | ((n & 0xffffffff) << 16) = (n >> 16) | (n << 16)

   得到 0001111010011100 0000001010010100

2. 以8位为一组，两两互相交换顺序:

   n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)

   得到10011100 00011110 10010100 00000010

3. 以4位为一组，两两互相交换顺序:

   n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)

   得到1100 1001 1110 0001 0100 1001 0010 0000

4. 以2位为一组，两两互相交换顺序:

   n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)

   得到00 11 01 10 10 11 01 00 00 01 01 10 10 00 00 00

5. 以1位为一组，两两互相交换顺序:

   n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)

   得到00 11 10 01 01 11 10 00 00 10 10 01 01 00 00 00

则，我们成功得到了逆序后的数字。

实现

整体时间复杂度为O(log2(k))，远优于之前O(k)的循环法；空间复杂度O(k)， 其中k为二进制的位数

public class Solution {
  private int[] leftMask = { 0, 0xaaaaaaaa, 0xcccccccc, 0xf0f0f0f0, 0xff00ff00, 0xffffffff };
  private int[] rightMask = { 0, 0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff, 0xffffffff };

  // you need treat n as an unsigned value
  public int reverseBits(int n) {
    return reverse(n, 5);
  }

  private int reverse(int n, int level) {
    if (level == 0) {
      return n;
    }
    
    // 这里我们需要用unsigned right shift - >>> 
    // 来避免signed right shift >> 在右移负数时使用1作为开头位数的填充符
    
    int leftPart = (n & leftMask[level]) >>> (1 << level - 1);
    int rightPart = (n & rightMask[level]) << (1 << level - 1);

    return reverse(leftPart, level - 1) | reverse(rightPart, level - 1);
  }
}

实现

我们在递归时，可以将左半部分与右半部分先拼在一起，这样就不用使用两个递归了。

public class Solution {
  private int[] leftMask = { 0, 0xaaaaaaaa, 0xcccccccc, 0xf0f0f0f0, 0xff00ff00, 0xffffffff };
  private int[] rightMask = { 0, 0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff, 0xffffffff };

  // you need treat n as an unsigned value
  public int reverseBits(int n) {
    return reverse(n, 5);
  }

  private int reverse(int n, int level) {
    if (level == 0) {
      return n;
    }
    
    int leftPart = (n & leftMask[level]) >>> (1 << level - 1);
    int rightPart = (n & rightMask[level]) << (1 << level - 1);

    return reverse(leftPart | rightPart, level - 1);
  }
}

思考

题目中最后提出：

如果这个函数将会被调用很多次，将如何优化？

因为是32位二进制数，在解法二中，递归次数只有5次。

在本题中，我们可以直接将其展开，以实现最大效率。

实现

public class Solution {
  // you need treat n as an unsigned value
  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;
  }
}