如何颠倒一个 32 位无符号整数的二进制位？（LeetCode 190）

简化版

把一个 32 位无符号整数的二进制位首尾颠倒（第 0 位和第 31 位互换、第 1 位和第 30 位互换……）。逐位法：循环 32 次，每次取出 n 的最低位，放到结果的对应高位——res = (res << 1) | (n & 1)，然后 n >>>= 1（无符号右移）。Java 里因为是有符号 int，取位和右移要用 & 1 和 >>> 避免符号位干扰。进阶可用分治交换（按 16-8-4-2-1 分块两两交换）做到 O(1)。

详细版

解法一：逐位反转（O(32)）

int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1);   // 结果左移腾位，接上 n 的最低位
        n >>>= 1;                      // n 无符号右移，处理下一位
    }
    return res;
}

解法二：分治交换（O(1)，进阶）

int reverseBits(int n) {
    n = (n >>> 16) | (n << 16);                                 // 交换高低 16 位
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);     // 每 16 位内交换字节
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);     // 每字节内交换 4 位
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);     // 每 4 位内交换 2 位
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);     // 相邻位交换
    return n;
}

逐位法核心：res 每轮左移一位腾出最低位，把 n 当前最低位接上去——相当于把 n 从低到高的位「倒着」堆进 res。
必须用 >>>：n 是有符号 int，负数用 >> 会补符号位出错。
复杂度：解法一 O(32)，解法二 O(1)（固定 5 步分治）。

完整版教学

一、题意：位的镜像翻转

把 32 位整数看成一个长度 32 的 0/1 串，要做的是把这个串首尾倒过来：原来的第 i 位，变成结果的第 31 - i 位。注意是「无符号」——我们只关心 32 个 bit 的排列，不管它当有符号数解释是正是负。

二、逐位法：从低位取、往高位堆

思路是「一边拆 n、一边搭 res」：

每一轮，取出 n 的最低位（n & 1）。
把它接到 res 的最低位上，但接之前先让 res 左移一位（res << 1）腾出位置：res = (res << 1) | (n & 1)。
然后 n >>>= 1，n 舍弃已处理的最低位。

循环 32 次。想清楚为什么这样就是反转：n 第一次取出的是第 0 位，它经过 32 次左移，最终被推到 res 的第 31 位；n 最后一次取出的是第 31 位，它刚放进 res 时在第 0 位、之后不再左移，留在第 0 位。恰好首尾对调——先取出的位被推得最高，后取出的留在最低，实现镜像。

三、为什么必须用无符号右移 `>>>`

Java 的 int 有符号。如果 n 是负数（最高位 1），用算术右移 >> 会在高位不断补 1，n >>= 1 永远清不空高位，导致取位错误甚至死循环。>>>（逻辑右移）高位补 0，才能把每一位干净地移下来。取最低位用 n & 1 本身没问题，关键是右移要 >>>。这是 Java 位运算处理负数/无符号的通用注意点。

四、解法二：分治交换（O(1) 常数步）

逐位法要 32 次循环。分治法用「二分交换」5 步搞定：

交换高 16 位和低 16 位；
在每 16 位块内，交换两个字节（8 位）；
在每字节内，交换两个 4 位；
在每 4 位内，交换两个 2 位；
交换相邻的两个 1 位。

每一步用一对掩码 + 移位并行完成所有块的交换（如 0xaaaaaaaa 取偶数位、0x55555555 取奇数位，右移/左移一位后 | 合并）。5 步下来，所有位都镜像到位。它是「归并式」的位反转，无循环、纯常数操作，适合对性能极致要求或面试炫技。

五、易错点与应用

>>> vs >>：逐位法负数必须 >>>，这是最高频错误。
循环固定 32 次：不能写「n != 0 就循环」——因为要输出满 32 位，高位的 0 也要参与移位占位。
应用背景：位反转在图像处理（FFT 的位反转置换）、网络字节序、哈希扰动里都有用。面试主要考对「逐位搬移 + >>>」的理解。
调用内置：Integer.reverse(n) 直接返回结果，但面试要求手写。

六、逐轮保持“已翻转前缀”不变量

固定处理 32 轮比“处理到 n 为 0”更稳，因为输入的前导零在输出中会变成尾随零，它们也属于 32 位反转的一部分。第 k 轮结束后，结果 res 的低 k 位等于原数低 k 位的逆序；下一轮先左移结果腾位，再接入原数当前最低位。

用 8 位演示 n=00010110
轮 1: res=00000000, 取 0
轮 2: res=00000001, 取 1
轮 3: res=00000011, 取 1
继续处理剩余 5 位（包括前导 0）
最终: res=01101000
校验：原第 i 位移动到结果第 7-i 位

校验维度	本题必须保持的结论
循环/递推不变量	完成 k 轮后，已经消费原数最低 k 位，并按相反顺序放入 res 的最低 k 位。
边界条件	必须恰好循环 32 次；Java 没有无符号 int 类型，读取位模式时用 `>>>`。
复杂度与代价	逐位法固定 32 轮，O(1) 时间 O(1) 空间；分治掩码法固定 5 轮交换。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：完成 k 轮后，已经消费原数最低 k 位，并按相反顺序放入 res 的最低 k 位。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“用 8 位演示 n=00010110”开始手推，最后应得到“校验：原第 i 位移动到结果第 7-i 位”。
边界复核：必须恰好循环 32 次；Java 没有无符号 int 类型，读取位模式时用 >>>。
代价复核：逐位法固定 32 轮，O(1) 时间 O(1) 空间；分治掩码法固定 5 轮交换。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“完成 k 轮后，已经消费原数最低 k 位，并按相反顺序放入 res 的最低 k 位。”这条正确性主线不能省。

八、常见误区与追问

误区：n 变成 0 就可以提前停止且不影响结果。 若仍按每轮左移的写法提前停止，会漏掉需要把已取位推到最终高位的剩余轮次。
误区：>> 与 >>> 对本题没有区别。 最高位为 1 时 >> 补 1，会污染后续取位；>>> 才按无符号位模式补 0。
误区：题目是反转十进制数字。 这里反转固定 32 位二进制位，和整数 123→321 完全不同。
追问：为什么每轮要先左移 res？ 它为新取出的位腾出最低位，并把较早取出的低位逐步推向更高位置。
追问：分治交换为何只需 5 轮？ 32 位按 16、8、4、2、1 位块逐层交换，块大小每轮折半。
追问：连续调用两次 reverseBits 会怎样？ 位反转是对合变换，固定宽度下执行两次会恢复原位模式。

九、加强记忆

颠倒二进制位 = 逐位「从低取、往高堆」：循环 32 次，res = (res << 1) | (n & 1) 把 n 当前最低位接到 res（res 先左移腾位），n >>>= 1 处理下一位。先取出的位被推到最高、后取的留最低，实现镜像。Java 负数必须用无符号右移 >>>（>> 补符号位会出错），且固定循环 32 次（高位 0 也要占位）。进阶用分治交换（16-8-4-2-1 五步掩码并行交换）达 O(1)。核心：>>> 别写成 >>。

简化版

详细版