0190. Reverse Bits

题目信息

题号:
  1. 颠倒二进制位

难度:

Easy

主题:

位运算、无符号整数、固定宽度

原题:

LeetCode 0190

重点:

把输入最低位依次折叠进答案,并用固定 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)。