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)``。