题目描述
这是 LeetCode 上的 190. 颠倒二进制位。
Tag : 「位运算」、「模拟」
颠倒给定的 32 位无符号整数的二进制位。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
进阶:
- 如果多次调用这个函数，你将如何优化你的算法？
示例 1：
输入: 00000010100101000001111010011100 输出: 00111001011110000010100101000000 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。 复制代码
示例 2：
输入：11111111111111111111111111111101 输出：10111111111111111111111111111111 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。 复制代码
提示：
- 输入是一个长度为 32 的二进制字符串
「对称位」构造
一个简单的做法是对输入的 nn 做诸位检查。
如果某一位是 1 的话，则将答案相应的对称位置修改为 1。
代码：
public class Solution { public int reverseBits(int n) { int ans = 0; for (int i = 0; i < 32; i++) { int t = (n >> i) & 1; if (t == 1) { ans |= (1 << (31 - i)); } } return ans; } } 复制代码
- 时间复杂度：intint 固定 32 位，循环次数不随输入样本发生改变。复杂度为 O(1)O(1)
- 空间复杂度：O(1)O(1)
「逐位分离」构造
另外一种做法是，每次都使用 nn 的最低一位，使用 nn 的最低一位去更新答案的最低一位，使用完将 nn 进行右移一位，将答案左移一位。
相当于每次都用 nn 的最低一位更新成 ansans 的最低一位。
代码：
public class Solution { public int reverseBits(int n) { int ans = 0; int cnt = 32; while (cnt-- > 0) { ans <<= 1; ans += (n & 1); n >>= 1; } return ans; } } 复制代码
- 时间复杂度：intint 固定 32 位，循环次数不随输入样本发生改变。复杂度为 O(1)O(1)
- 空间复杂度：O(1)O(1)
「分组互换」
事实上，可以对于长度固定的 intint 类型，我们可以使用「分组构造」的方式进行。
两位互换 -> 四位互换 -> 八位互换 -> 十六位互换。
代码：
public class Solution { public int reverseBits(int n) { n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1); n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2); n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4); n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8); n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16); return n; } } 复制代码
- 时间复杂度：如何进行互换操作取决于 intint 长度。复杂度为 O(1)O(1)
- 空间复杂度：O(1)O(1)
PS. 类似的做法我在 191. 位1的个数 也介绍过。如果大家学有余力的话，建议大家在纸上模拟一下这个过程。如果不想深入，也可以当成模板背过（写法非常固定）。但请不要认为「方法三」一定就比「方法一」等直接采用循环的方式更快。此类做法的最大作用，不是处理 int，而是处理更大位数的情况，在长度只有 32 位的 int 的情况下，该做法不一定就比循环要快（该做法会产生多个的中间结果，导致赋值发生多次，而且由于指令之间存在对 n 数值依赖，可能不会被优化为并行指令），这个道理和对于排序元素少的情况下，我们会选择「冒泡排序」而不是「归并排序」是一样的，因为「冒泡排序」常数更小。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.190 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
