企业官网建设流程全解析

这道题我在刷力扣的时候反复遇到过好几次，每次看到官方题解里那个二十多行的分治代码，都有点懵：明明就是个二进制反转，为什么能玩出花来？后来自己动手把三种解法都写了一遍，才终于弄明白其中的门道。

Reverse Bits（力扣190题）是一个标准的位运算基础题，题面很短：给定一个 32 位无符号整数，返回把它按二进制位翻转之后的结果。听起来简单，但真正写代码的时候坑不少——右移还是左移、无符号数在 Java 里怎么处理、为什么别人的代码一上来就拼一堆十六进制常量，这些细节如果不逐层拆开，看十遍题解也记不住。

这篇笔记我会从位运算的基础概念开始，把逐位反转、分治法（掩码法）两条主线都讲透，最后附上我实际踩过的几个坑和排查思路。适合正在刷力扣的算法新人，也适合准备面试想快速捡起位运算的人。

1. 题面拆解与位运算基础回顾

1.1 题目到底在说什么

先看题目的原始定义：reverseBits(43261596)，输入数字的二进制是00000010100101000001111010011100，期望输出964176192，它的二进制是00111001011110000010100101000000。

如果你把这两串二进制并排对照着看，规律非常直观：输入的第一位（最高位）变成了输出的最后一位（最低位），输入的倒数第二位变成了输出的正数第二位，整体就是一次首尾对称的镜像翻转。

很多人在这一步就急着写代码，结果翻了车。原因是题目给的是“二进制串反转”，但我们在代码里面对的却是整数。整数在内存里就是 32 个 0/1，你无法直接像切字符串一样reverse它，只能用位运算一位一位搬，或者用掩码成批地搬。这就是这道题真正的考察点：会不会用位运算符去操作二进制位，而不是题目背后的数学公式。

另外有个特别容易忽略的点：输入和输出都是“无符号 32 位整数”。注意，题目说的是“无符号”，但你在 JVM 里用int接它的时候，Java 的int是有符号的。比如输入4294967295（二进制全 1）根本没法直接塞进int。力扣对这类题通常用int代表那 32 个位，解析规则要理解成“只看二进制位，不管符号”，代码里必须配合>>>（无符号右移）来操作，否则遇到高位的 1 会出问题。这一点后面我专门用一节来说。

1.2 位运算基础：与、或、异或、移位

这道题里真正用得上的运算符有四组，扭清楚它们的关系，代码才写得顺：

• 按位与（&）：两个位都是 1 才得 1，常用于“提取某一位”。想拿到数字n的最低位，直接n & 1，结果是 0 或 1，这一位就“抠”出来了。
• 按位或（|）：只要一个位是 1 就得 1，常用于“把某一位拼到结果上”。
• 按位异或（^）：两个位不同才得 1。它有个操作上的价值：x ^ 0 = x，x ^ 1 = ~x。在 Reverse Bits 的查表法中会用到byte & 0xff这类掩码配合异或做字节反转，不过基础解法里用不太上。
• 移位（<< >> >>>）：左移右移的本质是“把二进制位整体挪动”，空出来的位补 0。特别注意 Java/C 里的>>>才是无符号右移，>>是算术右移，会保留符号位。

我用一句话总结：与用来提取、或用来拼装、移位用来搬运。Reverse Bits 的所有解法，本质都是“提取一位 → 搬运到目标位置 → 拼装到结果”，或者“提取一组位 → 整体平移 → 合并”。理解了这句话，题解里的所有代码都能看懂。

2. 逐位反转法的完整实现

2.1 核心思路：从低位搬到高位

逐位反转法，也挺形象：我们把输入数字的每一位单独拆开，再放到输出结果对应的对称位置上去。

具体来说，输入的第 0 位（最低位）要放到输出结果的第 31 位（最高位）；输入的第 1 位放到输出的第 30 位；以此类推。伪代码是这个样子：

result = 0 for i from 0 to 31: 取到 n 的第 i 位 把这一位放到 result 的第 31 - i 位

“取第 i 位”的实现是(n >> i) & 1：先把数字右移 i 位，让目标位变成最低位，然后按位与 1 把它抠出来。

“放到第 31 - i 位”的实现是(bit << (31 - i))：把它左移到目标位置。每次迭代把这个值累加到result上（用按位或），循环 32 次之后就完成了。

2.2 代码细节与边界情况

下面是完整的 Java 实现：

public int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { // 取出 n 的第 i 位 int bit = (n >> i) & 1; // 把它移动到 31 - i 的位置并合并到结果 result |= (bit << (31 - i)); } return result; }

这里有两个细节值得展开。

第一个关键是那个& 1。很多人会问：既然取出了bit，为什么不直接result |= (n & (1 << i))？区别在于，n & (1 << i)得到的是一个除了目标位为 1（或 0）之外全是 0 的大整数，直接|=上去确实也能把对应位写上。但这样写的意图不够清晰，而且代码里到处是1 << i，看着眼花。用(n >> i) & 1把位“抠”成 0 或 1 再移位，逻辑更直观，也不容易在后续调试时犯迷糊。

第二个关键是>>和>>>的选择。这里我用的是n >> i。如果 n 是负数（二进制高位为 1），>>右移时会把符号位往右带，导致高位一直填充 1，而不是 0。这对于我们“取第 i 位”这个操作来说其实是无所谓的——因为我们取了位之后立刻& 1，高位填的 1 不会影响最低位的提取结果。但如果你在别的地方用n >> i去构造一个低位连续数字，或者在做无符号右移的题，那建议一律写>>>，从习惯上规避问题。

2.3 复杂度分析与为什么它算“模板解法”

时间复杂度：循环 32 次，每次常数操作，O(1)。空间复杂度：只用了几个变量，O(1)。

无论输入多大，这题的时间复杂度恒定是 O(1)，因为 32 位是题面写死的，不会随输入规模变化。面试官问复杂度的时候要注意别答 O(n)，要答“固定迭代 32 次，O(1)”。

我自己的经验是，逐位法是位运算题的“兜底模板”。它慢不慢？不慢，因为 32 次循环对计算机来说是一瞬间的事。它好不好写？好写，思路 10 秒就能想清楚。唯一的缺点是每一步只处理一位，感觉上“不够聪明”。但作为面试里的保底方案，它永远能让你在 2 分钟内写出一道题并保证正确，不管题目怎么变，逐位提取思想的迁移性是最强的。后面遇到Hamming Weight、Power of Two、UTF-8 Validation这些题，你会发现它们也都是从“逐位抠位”延伸出来的。

3. 分治法：用掩码一次处理多位

3.1 掩码从哪来：以 2 为单位的交换

分治法的起点是一个朴素观察：反转 32 位，可以拆成“反转 16 位再互换”，而反转 16 位又可以拆成“反转 8 位再互换”……层层二分，最后只要解决最底层的“反转 1 位”问题即可。

这里“反转”两个字要特别小心。在分治语境里，我们的“反转”其实分两步：先把左右两个部分各自内部的位顺序反转，再把左右两部分的位置整体交换。举个 8 位例子，输入abcdefgh。

• 第一步（4 位一组）：交换相邻 4 位块，得到efghabcd。注意此时每个 4 位块内部顺序还没动，abcd还是abcd。
• 第二步（2 位一组）：在每 4 位块内交换相邻 2 位块，得到ghefcdab。
• 第三步（1 位一组）：在每 2 位块内交换相邻 1 位，得到hgfedcba。

三步做完，abcdefgh就变成了hgfedcba。这个思路完全适用于 32 位整数。

那怎么在代码里“交换相邻块”？答案是构造掩码，用位运算完成分区提取和位移合并。

3.2 经典分治实现与掩码推导过程

直接看最经典的代码：

public int reverseBits(int n) { n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16); n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8); n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4); n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2); n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1); return n; }

第一眼看这堆十六进制常量，很容易头皮发麻。我建议你拿笔自己推导一遍，理解了第一行，后面几行就是套娃：

• 0xFFFF0000= 二进制 1111111111111111 0000000000000000，它能把高 16 位保留下来，低 16 位清零。
• 把保留的高 16 位>>> 16，整体搬到低 16 位的位置。
• 同理，0x0000FFFF保留低 16 位，<< 16把它搬到高 16 位的位置。
• 两个部分按位或，完成“16 位块互换”。

再看第二行，0xFF00FF00的二进制是 11111111 00000000 11111111 00000000，它一次性保留下“8 位块级别”的奇数块（第 1、3 个字节），把偶数块清掉。右移 8 位、或上另外半边，完成 8 位块的互换。

后面的0xF0F0F0F0（轮流 4 个 1 和 4 个 0）、0xCCCCCCCC（二进制 11001100…）、0xAAAAAAAA（二进制 10101010…）同理，分别是 4 位、2 位、1 位块级别的交换。

我最初一直记不住这些掩码，后来找到一个方法：从第三行开始往前倒推。0xAAAAAAAA这种“1010 串”可以用1 << n快速构造，比如 32 位全 1 的0xFFFFFFFF，分别和 0xFFFFFFFF 做>>> 1或<< 1再异或，也能推出 0xAAAAAAAA 和 0x55555555。如果面试里担心临时忘记常量，你就当场算：

• 0xAAAAAAAA=0xFFFFFFFF ^ 0x55555555，写成二进制是 10101010101010101010101010101010。
• 0x55555555是 01010101010101010101010101010101。

只要记得“相邻位交换用 A/A 和 5/5”，“2 位一组用 C/C 和 3/3”，“4 位一组用 F/0”…… 十六进制常量其实是二进制的压缩书写，完全没必要硬背，建议你直接在 IDE 里跑一遍打印二进制看看效果。

3.3 逐位法和分治法的对比与选型

我的建议是：面试先答逐位法，再展示分治法作为优化。这样既体现了你能快速给出正确解，又展示了你知道更优技巧。实际工作中如果要做数据的二进制镜像、位交换，分治法的效率确实高，因为只需要几条指令，而且完全无分支，适合需要极致性能的场景。但如果你只是刷题练手，逐位法已经足够通过力扣的全部测试用例，因为数据规模根本不敏感。

4. 常见错误与排查技巧实录

4.1 右移还是左移：方向感混乱怎么破

这是新手最容易犯的错。明明题目说反转，结果写完代码一跑，输入输出完全不对，有时候还会得到负数。最典型的问题是把(n >> i) & 1里面的>>写成了<<，或者把结果移位方向搞反了。

我的排查方法是：取最高位和最低位做对照测试。写一个测试用例，输入0x80000000（只有第 31 位为 1），如果代码正确，反转后应该得到0x00000001（只有第 0 位为 1）。如果输出不对，立刻能确定是左移右移方向写反，或者掩码交换时位移位数不对。这个测试用例几乎能覆盖所有方向类 bug。

还有一个容易忽略的问题：如果用int存结果，左移时如果bit << 31得到的是负数（因为最高位变成了符号位），打印出来是一大串负数。这其实不影响二进制位的正确性，但如果你用System.out.println验证结果，看到负数会吓一跳。如果你想打印成可读的二进制检查，可以用：

System.out.println(String.format("%32s", Integer.toBinaryString(result)).replace(' ', '0'));

确保你看到的是完整的 32 位二进制串，而不是裸的十进制负数。

4.2 有符号数陷阱与语言差异

力扣题面写的是“无符号整数”，但 Java 没有无符号int。好消息是，Reverse Bits 这题在 Java 里仍然用int解题，因为题目测试用例期望的输出是一个十进制正整数，而 Java 的int在进制转换时会自动解释成二进制的 32 位模式。真正会出问题的是你手动把二进制字符串转整数时：

Integer.parseInt("11111111111111111111111111111111", 2);

这行代码会抛NumberFormatException，因为parseInt把它当超范围的正数来看。要处理这种情况得用：

Integer.parseUnsignedInt("11111111111111111111111111111111", 2); // 会得到 -1

建议你把“左移必须负数、解析用 parseUnsignedInt”这个意识刻进脑子里，很多位运算题都会在这里卡住。C++ 的uint32_t天然无符号，写起来更顺手；Java 这边多用>>>配合二进制位模式去思考，千万别被“十进制负数”干扰。

4.3 相似题目与扩展训练

Reverse Bits 做完之后，位运算还有几道经典的变体，我建议按顺序刷：

• 力扣 191. 位 1 的个数：计算一个整数二进制中有多少个 1。逐位法用n & 1计数即可，进阶可以用n & (n - 1)清零最低位的 1，循环次数等于 1 的个数。
• 力扣 231. 2 的幂：判断一个数是否为 2 的整数次幂。利用x & (x - 1) == 0快速判断。
• 力扣 136. 只出现一次的数字：用异或的性质x ^ x = 0，把成对的数字全消掉，剩下的就是答案。
• 力扣 268. 丢失的数字：异或同样能判断缺失值。

这几道题本质都是对位运算基本性质的灵活运用。每刷完一道，问自己一句：这题如果要求“不使用循环”还能做吗？这一步逼出来的解法，通常就是分治、查表或者公式法，这才是位运算进阶的路线。

最后分享一个我自己摸索出来的做题习惯：不要在天花板上背掩码，把0xAAAAAAAA这类常量当成二进制模式的压缩表示来理解。每次写位运算题之前，先在草稿纸上把目标数的二进制画出来，比如0xCCCCCCCC就是 1100 1100 1100 1100……，然后你就能自己推出掩码，而不用依赖记忆。这一招在面试现场尤其管用，因为人一紧张，背过的常量是容易混乱的，但二进制模式推导出来的东西很稳。