跳到主要内容

LeetCode 190. 颠倒二进制位

本节目标

在固定 32 位宽内，从低位取出每一位并依次写入答案。

这道题不是把“数字的有效二进制部分”反过来，而是把一个完整的 32 位无符号字反过来。它把二进制与位运算基础中的取位、移位组合成一个固定宽度的构造过程。

查看原题

题意与约束​

给定无符号 32 位整数 n，将它的 32 个二进制位从左到右颠倒，返回新的无符号 32 位整数。

  • 输入和返回值都在 0 到 2^32 - 1 之间。
  • C++ 接口为 uint32_t Solution::reverseBits(uint32_t n)。
  • Python 的 int 没有固定宽度，因此实现需要主动把输入限定为 32 位。

固定 32 位意味着什么​

数值写成二进制时通常省略前导零，但本题的前导零也是待颠倒的位置。例如 1 的 32 位表示是 000...0001；颠倒后是 100...0000，即 2147483648，而不是 1。

所以不能只循环到 n 变成 0。那种循环只会处理原数的有效位，无法把省略的前导零补到答案的低位，也无法让最低位的 1 移到第 31 位。无论 n 多小，都必须执行恰好 32 轮。

读取最低位并构造答案​

每轮先用 n & 1 读取当前最低位，再把已有的 answer 左移一位，为新读出的位腾出最低位：

answer = (answer << 1) | (n & 1)
n >>= 1

原数从低位向高位被读取；每个读出的位都接到 answer 的右侧。因此，原数的最低位会在后续不断左移，最后到达答案的最高位，顺序恰好被反转。

32 轮循环不变量​

设循环已完成 i 轮：

  • n 已右移 i 位，原来的低 i 位已经被读取。
  • answer 的低 i 位，正好按相反顺序保存原数的低 i 位。

第 i + 1 轮将 answer 左移，再追加原数的第 i 位，因此不变量继续成立。完成第 32 轮时，所有位置都已处理，answer 就是完整的位颠倒结果。

代码实现​

C++ 使用 uint32_t：它明确表示无符号 32 位宽，避免最高位为 1 时混入有符号数和算术右移的语义。Python 先用掩码 0xFFFFFFFF 执行 n &= 0xFFFFFFFF，把任意传入整数截成题目规定的低 32 位；计算结束后再次掩码，明确返回固定宽度结果。

C++17
#include <cstdint>

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t answer = 0;
        for (int bit = 0; bit < 32; bit++) {
            answer = (answer << 1) | (n & 1U);
            n >>= 1;
        }
        return answer;
    }
};

复杂度分析​

循环轮数固定为 32，时间复杂度为 O(1)；只使用 n、answer 和循环变量，空间复杂度为 O(1)。

易错点​

  • 写成 while n != 0：会忽略前导零，n = 1 会错误地得到 1。
  • 只右移输入而不构造答案：读取顺序正确不等于输出顺序已反转。
  • C++ 用 int：最高位、输出值和右移语义都可能受到有符号数影响，应使用 uint32_t。
  • Python 不做掩码：Python 的负数按位运算采用无限宽补码语义，不等同于题目的 32 位无符号字。

模式迁移​

当题目要求在固定宽度内重排位、序列化位字段或把低位流写入新整数时，可以复用“取最低位、左移答案、追加该位”的模式。若宽度不是 32，只需把循环次数和掩码同步改成目标位宽；固定轮数仍是保证前导零参与计算的关键。