1.题目

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

示例：

  1. 输入: 00000010100101000001111010011100
  2. 输出: 00111001011110000010100101000000
  3. 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
  4.      因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000
  6. 输入：11111111111111111111111111111101
  7. 输出：10111111111111111111111111111111
  8. 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
  9.      因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111

提示：

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

进阶:
如果多次调用这个函数，你将如何优化你的算法？

2.思路

我们这里首先了解几个概念，java的移位运算符：

java中有3种移位运算符：

<< : 左移运算符，不改变符号位，num << n 表示二进制左移n位，结果相当于 num * (2的n次方)

: 右移运算符，不改变符号位，num >> n 表示二进制右移n位，结果相当于 num / (2的n次方)

: 无符号右移，长度扩展为4字节，最高位都为0，但正数扩展位补0，负数扩展位补1。若无扩展，空位补0

n&1:按位与运算

  1. 将&符号两边的数字转化成二进制。
  2. 做按位与运算，每一位对应起来，按照简单的规则做就可以啦。
0&0 = 0 ;
0&1 = 0 ;
1&0 = 0 ;
1&1 = 1 ;

与反转十进制整数使用取模除十累加的方法类似：

十进制：ans = ans 10 + n % 10; n = n / 10;
二进制：ans = ans 2 + n % 2; n = n / 2;
但是，仅仅使用这种写法，会有一些问题，比如都要考虑是否整型溢出，Java的整数溢出后的二进制数会表示成负数（补码形式），Java中负数除以2会向零取整；比如：-3 / 2 = -1 而 -3 >> 1 = -2

然后还要考虑前导零，因为十进制是不考虑前面是否还有零的，比如100反转后就是1，不用写成001，而二进制要考虑前导零的问题。

所以综上所述，要使用位运算来避免溢出问题，同时循环32次。

因为一共只有32位，所以时间复杂度和空间复杂度都是O(1)。

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