0190. Reverse Bits
==================
题目信息
--------
:题号: 0190. 颠倒二进制位
:难度: Easy
:主题: 位运算、无符号整数、固定宽度
:原题: `LeetCode 0190 `_
:重点: 把输入最低位依次折叠进答案,并用固定 32 轮保留前导零对应的位置
题目重述
--------
给定一个 32 位无符号整数的位模式,将全部 32 个二进制位的顺序颠倒并返回结果。
若输入从高位到低位为 ``b31 b30 ... b1 b0``,输出必须是
``b0 b1 ... b30 b31``。位宽固定为 32,输入高位的零同样参与位置颠倒。
自建示例
--------
.. code-block:: text
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
.. code-block:: text
输入: 00000000000000000000000000000001
输出: 10000000000000000000000000000000
唯一的最低位 1 被移动到第 31 位,返回无符号值 2^31。
.. code-block:: text
输入: 00000000000000000000000000000000
输出: 00000000000000000000000000000000
C++ 实现
--------
.. code-block:: cpp
#include
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`` 取出。答案先左移一位,为新位腾出最低位置,再把取出的位
按位或进去:
.. code-block:: text
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``。前四轮答案变化为:
.. code-block:: text
读入位 计算 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)``。