0190. Reverse Bits¶
题目信息¶
- 题号:
颠倒二进制位
- 难度:
Easy
- 主题:
位运算、无符号整数、固定宽度
- 原题:
- 重点:
把输入最低位依次折叠进答案,并用固定 32 轮保留前导零对应的位置
题目重述¶
给定一个 32 位无符号整数的位模式,将全部 32 个二进制位的顺序颠倒并返回结果。
若输入从高位到低位为 b31 b30 ... b1 b0,输出必须是
b0 b1 ... b30 b31。位宽固定为 32,输入高位的零同样参与位置颠倒。
自建示例¶
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
输入: 00000000000000000000000000000001
输出: 10000000000000000000000000000000
唯一的最低位 1 被移动到第 31 位,返回无符号值 2^31。
输入: 00000000000000000000000000000000
输出: 00000000000000000000000000000000
C++ 实现¶
#include <cstdint>
class Solution {
public:
std::uint32_t reverseBits(std::uint32_t n) {
std::uint32_t reversed = 0U;
for (int processed = 0; processed < 32; ++processed) {
std::uint32_t next_bit = n & 1U;
reversed = (reversed << 1U) | next_bit;
n >>= 1U;
}
return reversed;
}
};
题解¶
字符串方案保留了不需要的表示¶
可以把输入格式化成恰好 32 个 '0'、'1' 字符,反转字符串,再解析回整数。它忠实
表达题意,却引入字符数组、格式化和解析;目标本来就是固定位模式,位运算可以直接读取和
写入每个位置。
若只从最高位逐个测试并写到最低位,需要不断构造位置掩码。更紧凑的做法是把输入视为从 最低位流出的位流,同时把答案向左生长。
一轮怎样消费一个位¶
当前输入最低位由 n & 1 取出。答案先左移一位,为新位腾出最低位置,再把取出的位
按位或进去:
next_bit = n & 1
reversed = (reversed << 1) | next_bit
n = n >> 1
输入右移后,已经处理的最低位被丢弃,下一原始位成为新的最低位。最早取出的原最低位会在 后续 31 轮中不断左移,最终到达答案最高位;最后取出的原最高位只写入答案最低位。
固定 32 轮为何不可省¶
把循环条件写成 while (n != 0) 会遗漏输入高位的零。以输入 1 为例,只执行一轮会得到
reversed = 1;正确过程还要为其余 31 个零执行 31 次答案左移,才能把这个 1 推到
最高位。
位模式的宽度是题目状态的一部分,不能由数值有效位数代替。即使 n 提前变成 0,剩余
轮次仍会取出零并移动已经构造的答案;全零输入也必须从同一个固定宽度语义得到全零输出。
循环不变量¶
设原输入从低到高的位为 b0,b1,...,b31。完成 t 轮后:
n等于原输入逻辑右移t位,最低位是下一个尚未处理的bt;reversed的低t位从高到低依次为b0,b1,...,b(t-1);reversed的更高位仍为零。
初始化 t = 0 时答案为零、输入未移动,不变量成立。每轮答案左移后追加 bt,使已
处理序列增长一位;输入右移使 b(t+1) 成为下一位,不变量推进。t = 32 时,答案
从高到低正是 b0,b1,...,b31,所有位置完成颠倒。
具体状态走读¶
取十进制 13,其低位从低到高是 1、0、1、1。前四轮答案变化为:
读入位 计算 reversed
1 0 * 2 + 1 1
0 1 * 2 + 0 2 即二进制 10
1 2 * 2 + 1 5 即二进制 101
1 5 * 2 + 1 11 即二进制 1011
此后输入已经为 0,但还要处理 28 个高位零,答案继续左移,最终得到
1011 后接 28 个零。若按数值变零提前停止,只会错误返回 11。
无符号类型的意义¶
std::uint32_t 明确提供 32 位无符号位模式。其右移在高位补零,不会像有符号负数右移
那样复制符号位;左移按无符号模运算保留低 32 位,也正好符合目标宽度。算法处理的是位
位置,不受最高位为 1 时数值显示方式影响。
正确性与复杂度¶
循环不变量证明每轮按原低位到高位的顺序读取一个位,并按相反方向构造答案;固定 32 轮后 恰好处理所有位置。因此返回值是完整 32 位反转。
循环次数固定为 32,按题目位宽可记为 O(1);若把位宽一般化为 W,时间为
O(W)。只维护输入副本、答案、当前位和计数,额外空间为 O(1)。