LeetCode 190. 颠倒二进制位
题目描述
题意分析
将整数视为固定长度为 32 的二进制位串，把全部位的顺序颠倒：原第零位移到第三十一位，原第三十一位移到第零位，其余位置依次对应。
前导零也是这 32 位的一部分，不能只反转从最高位的一开始的有效数字。返回的是反转后的位模式；Java 用有符号
int承载时，最高位为一的结果可能显示为负数，但位串仍然正确。
解法：逐位取出并拼接
核心思路
[!blue]
从输入最低位开始读取，就已经按目标结果从高位到低位的顺序取得字符。每轮用
n & 1取出当前最低位，将结果左移一位腾出位置，再把这一位用按位或放到结果最低位。输入随后右移一位，下一轮读取原来的下一位。经过
k轮，结果的低k位保存原输入低k位的倒序；继续左移追加会保持这一关系。完整执行 32 轮后，原最低位被推到最高位，所有位置完成反转。循环次数必须固定。即使输入已经右移为零，剩余高位零也仍需依次追加，让结果中已有的一移动到应在的位置。
Java 使用无符号右移
>>>表示高位补零，Go 用uint32做相同操作。这里判断正确性依据是固定取完 32 个原始位，而不是数值的正负。原题多次调用的进阶可进一步预处理字节反转表，见后面的解法。
解题步骤
- 将结果初始化为零。
- 固定循环 32 次，每次先把结果左移一位。
- 用按位或追加输入当前最低位，再将输入无符号右移一位。
- 返回保存了全部反转位的结果。
代码实现
public class Solution {
public int reverseBits(int n) {
int res = 0;
// 完整位宽包含前导零，固定处理三十二位
for (int i = 0; i < 32; i++) {
// 先腾出最低位，再填入输入的当前最低位
res = (res << 1) | (n & 1);
n >>>= 1;
}
return res;
}
}
func reverseBits(num uint32) uint32 {
var res uint32
// 完整位宽包含前导零，固定处理三十二位
for i := 0; i < 32; i++ {
// 先腾出最低位，再填入输入的当前最低位
res = (res << 1) | (num & 1)
num >>= 1
}
return res
}
复杂度分析
- 时间复杂度：$O(1)$，固定执行 32 轮。
- 空间复杂度：$O(1)$，只保存结果和循环状态。
关键点总结
[!green]
- 从输入低位开始取，按顺序追加到结果，就实现首尾逆转。
- 前导零参与位置变化，不能在输入归零时提前停止。
- 数值类型的符号解释不改变位模式，不应额外修改返回值。
进阶解法：预处理字节反转表
核心思路
[!blue]
多次调用时，输入虽然不同，但一个字节只有 256 种可能值。可以预先计算每个八位值的反转结果，后续直接查表，避免每次重新进行 32 轮逐位操作。
将输入拆为从低到高的四个字节。完整位反转分成两件事：每个字节内部反转八位，同时把四个字节的先后顺序反过来。因此原最低字节反转后放到结果最高八位，第二个放到次高八位，依次完成。
用
& 255提取一个字节，无符号右移分别取出其他三个字节。每个查表结果都在零到 255 之间，左移到目标位置后四段互不重叠，直接按位或即可合并。表在 Java 类初始化或 Go 包初始化时只建立一次，所有调用共享。不要把建表过程放进每次调用里，否则重复初始化会抵消这项优化的作用。
解题步骤
- 对零到 255 的每个数，执行八轮逐位反转，保存到固定表。
- 每次调用提取输入的四个八位片段。
- 查表反转片段内部，再分别放到第三、第二、第一、第零字节位置。
- 按位或合并四段并返回。
代码实现
class Solution {
private static final int[] REVERSED = buildTable();
private static int[] buildTable() {
int[] table = new int[256];
for (int value = 0; value < table.length; value++) {
int current = value;
for (int bit = 0; bit < 8; bit++) {
table[value] = (table[value] << 1) | (current & 1);
current >>>= 1;
}
}
return table;
}
public int reverseBits(int n) {
return (REVERSED[n & 255] << 24)
| (REVERSED[(n >>> 8) & 255] << 16)
| (REVERSED[(n >>> 16) & 255] << 8)
| REVERSED[(n >>> 24) & 255];
}
}
var reversedBytes = buildReversedBytes()
func buildReversedBytes() [256]uint32 {
var table [256]uint32
for value := range table {
current := uint32(value)
for bit := 0; bit < 8; bit++ {
table[value] = (table[value] << 1) | (current & 1)
current >>= 1
}
}
return table
}
func reverseBits(num uint32) uint32 {
return (reversedBytes[num&255] << 24) |
(reversedBytes[(num>>8)&255] << 16) |
(reversedBytes[(num>>16)&255] << 8) |
reversedBytes[(num>>24)&255]
}
复杂度分析
- 时间复杂度：一次性建表为 $O(256\times8)$，每次调用固定进行四次查表和若干位运算，均为 $O(1)$。优化减少每次调用的常数工作量，不改变渐进复杂度。
- 空间复杂度：$O(1)$，共享表固定包含 256 项，单次调用只使用常数空间。
关键点总结
[!green]
- 用有限字节状态的预计算，复用多次调用中的重复工作。
- 字节内部反转与字节顺序反转共同组成完整 32 位反转。
- 共享表只初始化一次，调用次数越多，预处理越容易摊薄。
易错点总结
[!yellow]
- 用输入是否非零决定循环结束，会漏掉高位零应产生的后续左移。
- 先填最低位再左移，会在最后额外多移一次，顺序应为先左移再填位。
- 取绝对值或清除结果符号位，会破坏正确的反转位串。
- 在本实现固定 32 次取低位的前提下，Java 算术右移不会提前读到补入位，不能笼统说替换为
>>就必然错误；使用>>>是为了清楚表达补零语义。- 查表法只反转每个字节内部还不够，四个字节之间的位置也必须倒序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 05.07. 配对交换 | 简单 | 同样移动固定宽度的位模式，原题只交换相邻位，本题反转全部位序。 |