LeetCode 190. 颠倒二进制位

2021-08-20 HGNULB 约 7 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动拼多多面试经典 150 题

题目描述

✅ 190. 颠倒二进制位

题意分析

给一个 32 位无符号整数，把它的二进制表示整体首尾颠倒，返回颠倒后对应的数。原来的第 0 位变成第 31 位，第 1 位变成第 30 位，依此类推。

「32 位」是硬性规定而不是根据数值大小推断的：即使输入是 1，也必须当成 0000...0001 这 32 位来翻转，结果是 $2^{31}$，而不是简单地把「有效位」翻过来得到 1。这决定了循环次数必须固定为 32，不能写成「n 不为 0 就继续」。

题目按无符号解释，但 Java 没有无符号 int，输入会以补码形式落在 int 里，可能是负数。这带来两处影响：右移必须用无符号右移，返回值也要允许是负数（判题会按无符号打印）。Go 的签名直接是 uint32，反而没有这个坑。

边界包括：输入为 0 时结果是 0；输入的最高位为 1（Java 里表现为负数）时不能被符号扩展污染；结果的最高位为 1 时 Java 里会显示成负数，这是正常的。

解法：逐位取出并拼接

核心思路

最容易想到的是先把数转成 32 位二进制字符串，反转字符串再解析回整数。它能过，但用库函数绕开了考点，而且分配了额外的字符串空间，面试中会被要求重写。

直接在位上操作的思路是：把原数看成一条从低位到高位的比特流，把答案看成一个从高位往低位逐渐填满的容器。每一轮从原数取出最低位，塞进答案的最低位，然后把答案整体左移——等价于每次给答案「腾出一格」再填。

具体到写法，标准的两行是 res = (res << 1) | (n & 1) 和 n >>>= 1。第一行先把已经收集到的位整体左移一格，空出最低位，再用 n & 1 取出原数当前的最低位填进去；第二行把原数右移，让下一位来到最低位。

由此得到循环维护的不变量：执行完第 i 轮后（i 从 1 计数），res 的低 i 位恰好是原数低 i 位的逆序，而 n 的低位已经推进到原数的第 i 位。第 1 轮把原数第 0 位放进 res 的第 0 位；第 2 轮 res 左移使它挪到第 1 位，原数第 1 位落到第 0 位……循环 32 轮后，原数第 0 位被左移了 31 次正好停在第 31 位，第 31 位则停在第 0 位，整体完成翻转。

这个不变量也解释了为什么必须固定循环 32 次：如果写成「n 非零就继续」，高位的那些 0 就不会被计入左移次数，res 不会被推到正确的高位上。

Java 里的 >>> 是关键。带符号右移 >> 会在高位补符号位，输入为负数（最高位是 1）时高位会不断补 1，n 永远不会变成 0，虽然本题循环次数固定所以不会死循环，但取出的位全是错的。Go 里 num 是 uint32，>> 本身就是逻辑右移，不存在这个问题。

解题步骤

初始化 res = 0，它是逐步填充的答案容器。

固定循环 32 次，不依赖 n 是否已经变成 0。这一条直接对应「题目规定处理 32 位」的题意，前导零也必须参与翻转。

每轮先做 res << 1，给最低位腾出空间。先移位再填位的顺序保证了最后一次填入的位不会被多移一次——如果写成先填后移，答案会整体左移一格并丢掉最高位。

用 n & 1 取原数最低位，与左移后的 res 做按位或写入。用 | 而不是 + 是习惯问题，此处两者等价，因为被写入的那一位一定是 0。

把 n 无符号右移一位。Java 必须用 >>>；Go 因为类型是无符号整数，>> 即可。

32 轮结束返回 res。

以输入 n = 43261596（二进制 00000010100101000001111010011100）走一遍，只跟踪前几轮和整体结果。

初始 res = 0。第 1 轮：n & 1 = 0，res = (0 << 1) | 0 = 0；n 右移后最低位变成原来的第 1 位。第 2 轮：原数第 1 位是 0，res 仍是 0。第 3 轮：原数第 2 位是 1，res = (0 << 1) | 1 = 1。第 4 轮：原数第 3 位是 1，res = (1 << 1) | 1 = 3（二进制 11）。第 5 轮：原数第 4 位是 1，res = (3 << 1) | 1 = 7（111）。

可以看到 res 正在从高位往低位地重建原数的逆序：原数最低的几位 ...11100 反过来读是 00111，与 res 目前的 111 前面还会补上后续的位一致。

继续走完 32 轮，res 的二进制为 00111001011110000010100101000000，对应十进制 964176192，正是题目样例的期望输出。

再看一个能暴露 >> 与 >>> 差异的用例：n = -3（无符号看是 4294967293，二进制 11111111111111111111111111111101）。正确翻转结果是 10111111111111111111111111111111，即无符号的 3221225471。若用带符号右移，n 的高位会持续补 1，第 2 轮之后取出的最低位恒为 1，结果会变成全 1 的 -1，明显错误。

代码实现

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) | (n & 1);
            n >>>= 1;
        }
        return res;
    }
}

func reverseBits(num uint32) uint32 {
    var res uint32
    for i := 0; i < 32; i++ {
        res = (res << 1) | (num & 1)
        num >>= 1
    }
    return res
}

复杂度分析

时间复杂度：$O(1)$，循环次数固定为 32，与输入数值无关，每轮只做常数次位运算。

空间复杂度：$O(1)$，只用一个累加变量和循环下标，没有任何额外容器。

关键点总结

位翻转的通用模板是「答案左移腾位 + 原数最低位填入 + 原数右移」，三步顺序固定；同样的模板换成十进制的乘十、取模、除十，就是整数反转题。

循环次数由题目定义的位宽决定，不能由数值提前终止——前导零同样携带位置信息，提前结束会让结果整体错位。

Java 没有无符号整数，凡是把 int 当比特容器用的题都要条件反射地用 >>>；>> 会做符号扩展，把高位污染成全 1。

判题按无符号解释结果，Java 里返回负数是正常现象，不要为了「看起来是正数」去加任何修正。

面试视角：写完逐位法后，面试官大概率会问「如果这个函数被调用很多次怎么优化」。标准答案有两个：一是按字节分块打表缓存（把 32 位拆成四个 8 位，预处理 256 项的翻转表），二是分治交换——先两两交换相邻位，再交换相邻两位组、四位组、八位组、十六位组，用五步掩码运算完成，形如 n = ((n & 0x55555555) << 1) | ((n >>> 1) & 0x55555555)。能主动说出分治法是明显加分项。

易错点总结

错误写法：Java 里用 n >>= 1 而不是 n >>>= 1 → 用例 n = -3，符号位不断向高位补 1，取出的低位从第 2 轮起恒为 1，返回 -1，正确答案对应无符号的 3221225471。

错误写法：循环条件写成 while (n != 0) → 用例 n = 1，只循环一次就退出，返回 1，正确答案是 -2147483648（无符号的 2147483648）。

错误写法：把两行的顺序写反，先填位再左移，如 res |= (n & 1); res <<= 1; → 用例 n = 1，最后多移了一位，最低位被挤出，结果整体错位一格。

错误写法：循环次数写成 31 或 33 → 用例 n = 1，31 次时结果只有 $2^{30}$，33 次时最高位被移出丢失，两者都错。

错误写法：用 n % 2 代替 n & 1 且 n 为负 → 用例 n = -3，Java 里 -3 % 2 等于 -1 而不是 1，或运算后污染 res 的全部高位。

错误写法：把 res 声明成 long 并在最后强转 → 用例 n = -1，左移过程中 res 累积到 64 位的全 1，强转回 int 后虽仍是 -1 碰巧正确，但 n = -3 这类用例上中间值的高 32 位会带上垃圾，逻辑不再可控。

错误写法：Go 里把参数或 res 声明成有符号的 int32 → 用例 num = 4294967293，res << 1 在最高位溢出触发未定义的符号翻转，且 >> 变成算术右移，结果全错。

错误写法：为了「让结果是正数」而在返回前加绝对值或与 0x7FFFFFFF 相与 → 用例 n = 1，正确结果的最高位就是 1，被掩码抹掉后返回 0。

错误写法：转字符串反转再解析时用 Integer.parseInt → 用例 n = 1，翻转后的字符串是 10000...0，超出有符号 int 范围直接抛 NumberFormatException，必须用 Integer.parseUnsignedInt。

错误写法：认为输入为 0 需要特判 → 用例 n = 0，循环 32 次每次都填 0，自然返回 0，多写的特判没有价值反而可能写错分支。

错误写法：用 Integer.reverse(n) 直接返回 → 库函数正是本题要考的东西，面试中等于没做，实现时必须手写。

相似题目

题目	难度	考察点
7. 整数反转	中等	十进制版的同一模板，重点变成反转后溢出的判断
191. 位1的个数	简单	只统计不重排，可用 `n & (n - 1)` 按 1 的个数循环
剑指 Offer 15. 二进制中1的个数	简单	191 的中文版，同样要注意 Java 里负数的无符号右移
338. 比特位计数	简单	批量求 0 到 n 的位数，可用 `f[i] = f[i >> 1] + (i & 1)` 递推
405. 数字转换为十六进制数	简单	每次取四位而非一位，同样依赖无符号右移处理负数
231. 2 的幂	简单	位运算判定而非重排，核心是 `n > 0 && (n & (n - 1)) == 0`