企业官网建设流程全解析

每天做一道算法题的好处，就是能逼自己把“好像会了”变成“真的会了”。今天这道190题，颠倒二进制位，表面上看是把一个32位无符号整数的二进制表示倒过来，实际上考的是你对位运算、掩码设计和“空间换时间”这三件事的掌握程度。我第一次做的时候，第一反应是转成字符串再reverse，后来发现，这条路走得通，但完全对不起这道题背后的位运算思维。

先把问题说清楚：输入一个32位无符号整数，比如43261596，它的二进制是00000010100101000001111010011100，要求输出964176192，也就是把它倒过来变成00111001011110000010100101000000。要注意的是，这题针对的是32位长度，不是整数本身的“有效长度”，二进制左侧的一堆0也要参与颠倒。这道题适合刚接触位运算的入门者，也适合想在面试前把掩码分治技巧彻底吃透的进阶选手。接下来我把几种思路从简到繁、从慢到快完整过一遍，结尾再补充一些我实际提交时踩过的坑。

1. 题目拆解与核心思路

1.1 它在考什么

这道题最直接的要求是“把二进制位反过来”，但背后隐含的知识点比想象中多。第一是对二进制表示的理解，得清楚“第0位”和“第31位”的概念；第二是对移位操作语义的掌握，逻辑右移和算术右移的区别、左移带来的低位补0问题，都会影响结果的正确性；第三是性能意识，32次循环能不能优化、查表法值不值得用，都是面试官想听到的讨论点。

很多人一开始会走字符串这条路：把整数转成二进制字符串，去掉0b前缀，用padStart(32, '0')填满32位，再反转字符串，最后parseInt转回整数。这个思路本身没错，在工程代码里甚至算一种“可读性优先”的写法。但问题在于，一旦题目要求在高频调用场景下使用，字符串和数字之间的反复转换就是完全不必要的开销。更重要的是，字符串方案无法迁移到其它位运算题目上，比如格雷码、状态压缩DP、子集枚举，这些场景只认位运算。

所以我的建议是，这道题必须用纯位运算解，而且最好把三种方案都写一遍：循环逐位、掩码分治、查表。这不仅是做对一道题，而是通过一道题把位运算家族的核心套路都过一遍。

1.2 为什么位运算是正路

位运算之所以是正路，核心在于它直接操作二进制位，不需要任何中间表示转换。n & 1能取出最低位，n >> 1能丢弃最低位，这两条指令组合起来，就是把一个整数看成一个比特流，从头到尾扫描一遍。

打个比方，字符串方案像把一本书每一页拍照存进手机，再按相册倒序翻一遍；位运算方案则是直接在书脊上做文章，把整本书从中间拆开、交换位置、再不停细分，最后页序自然就反过来了。后者快，而且省内存。

另外，32位这个固定长度给优化提供了空间：循环次数固定为32，完全可以用“分治”的思路把复杂度从32次迭代压到5轮位操作。这也是这道题为什么经典的原因——它同时考察了“线性扫描”和“二分式重组”两种模型。

2. 基础解法：逐位颠倒的循环实现

2.1 核心逻辑与代码

先上最朴素的循环解法，直接用uint32_t防止类型转换的坑：

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

代码只有五行核心逻辑，但每一行都能拆出不少问题。

n & 1是取出n的最低位，也就是当前要处理的比特位。result << 1是把已有的结果整体左移一位，给新比特腾出最低位位置，再用按位或|把它填进去。最后n >>= 1让原来的次低位变成新的最低位，方便下一轮继续取。

这里最值得想明白的是为什么result不用先清空再赋值：每一轮result都会先左移一位，所以之前累积的比特会依次往高位走，而新取出的比特永远落在最低位。循环结束后，原数的第0位跑到了结果的第31位，原数的第31位跑到了结果的第0位，正好完成颠倒。

2.2 复杂度、边界与优化点

时间复杂度是O(1)，因为无论输入是什么，循环次数恒为32次。空间复杂度是O(1)。从大O角度看，这个解法已经“最优”了，但常数上还有压缩空间。

我在实际测试中发现，循环版最耗时的是每轮迭代里的分支判断和循环变量更新，哪怕现代CPU分支预测很准，跳转和循环开销仍然存在。在LeetCode这种题量级上，循环版耗时大概在0到4毫秒之间波动，而分治版可以稳定在0到1毫秒。如果是嵌入式环境或者高频调用，这个差距会明显得多。

边界情况也要注意：输入0时，32轮都是取0、填0，最后结果还是0，没有问题；输入0xFFFFFFFF时，每一轮取出的都是1，左移填充后依然是0xFFFFFFFF；输入0x80000000时，只有最高位是1，循环结束后结果应该是1，也不会出错。循环版在所有边界上都表现稳定，这是它的一个优点。

3. 进阶优化：分治法与掩码设计

3.1 先交换相邻位，再逐层扩大

分治法的核心思想可以概括成一句话：先每2位为一组进行交换，再每4位一组交换，再每8位、每16位，最后整体交换高低16位。整个过程类似归并排序的自底向上过程，只不过归并排序合并的是有序数组，这里合并的是比特块。

我们用具体例子感受一下。假设有一个8位二进制数abcdefgh，第一步把每1位当作一组进行交换，得到badcfehg；第二步把每2位一组交换，得到dcbahgfe；第三步把每4位一组交换，得到hgfedcba。看到没有，只需要3轮，8位就完全反过来了。32位版本只需要5轮，因为2^5 = 32，每轮交换的块大小翻倍，从1到2、4、8、16。

这个思路比循环版“逐位搬”要快，原因是它跳过了“从最低位移到最高位”的长途运输过程，每个比特移动的距离都很短：第一次只和邻居交换，第二次最多移动2位，第三次最多4位，依此类推。总移动距离远小于循环版每个比特最多移动31位。

3.2 五轮掩码的推导与实现

分治法的关键在掩码设计。先看第一轮，交换相邻1位，掩码是0x55555555。为什么是这个数？因为5的二进制是0101，重复8次就是01010101...，正好在每两位的低位上放1。这个掩码用来“提取奇数位”（从第0位开始算），配合移位就能完成交换。

具体分三步：第一，n & 0x55555555取出所有奇数位，左移1位，让它们跑到偶数的位置上；第二，(n >> 1) & 0x55555555把原偶数位的值移到奇数位，再用同样的掩码过滤，只保留交换后应该留下的位；第三，把两部分按位或合并。

class Solution { public: uint32_t reverseBits(uint32_t n) { n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555); n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333); n = ((n & 0x0F0F0F0F) << 4) | ((n >> 4) & 0x0F0F0F0F); n = ((n & 0x00FF00FF) << 8) | ((n >> 8) & 0x00FF00FF); n = (n << 16) | (n >> 16); return n; } };

第二轮的掩码0x33333333，二进制是001100110011...，每两位一组，组内的低两位是1，用来提取相邻的2位块。<< 2和>> 2把2位块整体交换。

第三轮掩码0x0F0F0F0F，二进制是0000111100001111...，每4位一组交换。第四轮0x00FF00FF，二进制是00000000111111110000000011111111，每8位一组交换。最后一轮不需要掩码，直接n << 16 | n >> 16，把高低16位整体交换，因为无符号整数的左移会在低位补0，右移会在高位补0，两者按位或正好互补。

我一直认为分治法的难点不是背代码，而是理解掩码为什么长这样。我自己的习惯是先写一个8位版本的推导，把0101、0011、00001111这些模式在纸上列一遍，再扩展到32位。一旦看懂了，0x55555555这种长数字就再也不需要死记硬背。

4. 查表法与其他优化方向

4.1 用空间换时间

查表法适合“同一份表会被反复查”的场景。这题可以把8位整数的颠倒结果预先算好，存到一张长度256的表里，然后每次处理4个字节，每个字节查一次表，最后拼起来。

先说表的构建。可以用一个小循环，对0到255的每个数做8次位运算：

uint8_t rev[256]; for (int i = 0; i < 256; i++) { uint8_t v = i, r = 0; for (int j = 0; j < 8; j++) { r = (r << 1) | (v & 1); v >>= 1; } rev[i] = r; }

表建好之后，翻转32位整数的逻辑就非常直接了：

uint32_t reverseBits(uint32_t n) { return (uint32_t)rev[n & 0xFF] << 24 | (uint32_t)rev[(n >> 8) & 0xFF] << 16 | (uint32_t)rev[(n >> 16) & 0xFF] << 8 | (uint32_t)rev[(n >> 24) & 0xFF]; }

这里的关键点有两个。第一，第0个字节查完表后要放到结果的最高位，所以左移24位；第3个字节要放到最低位，不左移。第二，查表结果要显式转成uint32_t再移位，否则在某些编译器上，uint8_t隐式转换后可能被当成有符号类型处理，导致意外的高位填充。

4.2 面试或竞赛中如何选择方案

很多人在面试时拿不定主意：到底应该写循环版、分治版还是查表版？我的建议是，先把循环版写出来，保证正确性和可读性，然后主动提一句“这个可以优化到常数级的5次位操作”，把分治版写出来。如果面试官感兴趣，再补充查表法。

查表法的优点是查询次数少，4次查表加3次移位就能完成；缺点是需要初始化表，如果整个程序只调用一次，初始化表的成本反而不划算。在LeetCode这类在线评测平台上，查表法的运行时间并不比分治版有压倒性优势，因为输入规模太小、调用次数太少。真正能体现查表法威力的是那些“在一个循环里反复翻转不同整数”的场景，比如图像处理中的像素级操作。

如果想再压缩，可以只建一张16位的表，长度是65536，然后用两次查表完成32位翻转。这属于“空间换时间”的极端版本，竞赛中偶尔见到，日常工作里我不建议，因为65536个元素的缓存命中率和内存占用都需要权衡，256大小的表已经够用了。

5. 高频踩坑与排查实录

5.1 常见错误速查表

很多人在实盘提交时踩过的坑，比想象中要隐蔽。我整理了一张速查表，每一行都是我或身边朋友真实遇到过的。

5.2 关键边界测试用例

我自己提交前会固定跑这几组测试，确保万无一失：

第一组是0转0，它验证的是全0场景，如果代码里有while(n)这种写法，这里就废了。第二组是0xFFFFFFFF转0xFFFFFFFF，验证全1场景，适合测掩码分治时有没有把某些位误伤掉。第三组是0x80000000转1，验证最高位的1能否顺利搬到最低位，这个用例对手写掩码尤其关键。第四组是0x0000FFFF转0xFFFF0000，验证低16位翻转后是否恰好到了高位。

还有一个很有趣的测试是43261596，LeetCode官方示例，答案964176192。这两组数字在二进制上完全镜像，肉眼直接看十进制很难反应过来，所以建议先转成二进制对一下再提交，避免被预期输出误导。

我在实际调试时发现，最让人觉得“莫名其妙”的错，是JavaScript版本的结果偶尔变成负数。原因很简单：JS的位运算会把结果解释为32位有符号整数，一旦最高位是1，返回的就是负值。解决办法是在返回前加一个>>> 0，强制转成无符号32位整数。这个坑在LeetCode里不算典型，但换到真实项目里就特别容易翻车，因为浏览器控制台打印负数也不会报错，排查起来很费劲。

6. 我的实操心得与后续建议

6.1 这类题怎么练

如果你刚开始刷位运算题，我建议不要直接跳到一个解法就提交，而是把“字符串法、循环法、分治法、查表法”四种都写一遍。四版代码都能运行之后，再对比它们的耗时和可读性，这比单纯追求提交通过要有效得多。

尤其推荐亲手画一遍分治法的每一轮状态。拿0x12345678当例子，写一个小的测试脚本，每轮操作后打印十六进制结果，观察数字如何一步步变成镜像。这一步做完，你对掩码的直觉会有质的提升。之后遇到“逆序二进制位”、“格雷码生成”这类题目，你会条件反射地想到掩码分治。

另外建议把这题和136. 只出现一次的数字、191. 位1的个数放一起刷，它们合起来能帮你建立完整的位运算工具箱：与或非、移位、掩码提取、计数、翻转。以后再碰到任何状态压缩DP的题，处理二进制状态的时候会顺手很多。

6.2 延伸运用

颠倒二进制位这件事本身在很多地方都会用到。比如CRC校验算法里，数据位需要按位反转才能匹配某些多项式；FFT算法中的蝶形运算需要把数组下标做比特反转；哈希散列中也有人用位反转来打散低位集中的数据。还有图形学里的二进制蒙版处理，偶尔也需要对位序做调整。

如果你做嵌入式或网络协议相关的开发，大概率会在调字节序时再次遇到“位级别反转”的需求。到那个时候，用分治法而不是逐位循环，节省的可能就是整包数据的处理时间。

我个人在实际操作中的体会是，像190. 颠倒二进制位这种题，第一次做感觉是死记硬背，第二次做开始理解掩码，第三次做才能在脑内直接推演每一轮交换后的比特流变化。把这三次做完，位运算基本就过关了。最后再分享一个小技巧：遇到十六进制掩码记不住时，先写二进制的重复模式，再四位一组转十六进制，又快又不容易错。这套方法我用了很多年，实测下来比硬背靠谱得多。