codeforces-go 位运算实战:LeetCode 190 反转二进制位的分治与并行掩码法
codeforces-go 位运算实战:LeetCode 190 反转二进制位的分治与并行掩码法
导读
本文以 leetcode/problems/190.md 为核心,系统讲解 LeetCode 190「颠倒二进制位」(Reverse Bits)的分治 + 位运算并行解法:先以 8 位整数建立直觉,再推广到 32 位,给出 Python / Java / C++ / Go 四语言完整实现、掩码常量语义、复杂度分析以及各语言库函数写法。结合本仓库 copypasta/bits.go 的位运算模板库,你还能看到这套「按位块交换」的递归思维如何在更复杂的竞赛题目(如线段树的区间 swap & reverse)中复用,从而做到举一反三。
一、问题直觉:用分治思考反转
反转一个二进制整数,最直观的写法是逐位提取再逐位放置,但那样需要循环 32 次。190.md 给出的切入点是:把反转当成一个分治问题。
以反转一个 8 位整数为例,记作 12345678,目标是得到 87654321。分治的思考路径分三步:
- 递归反转左半
1234,得到4321; - 递归反转右半
5678,得到8765; - 交换
4321与8765,得到87654321。
反转 1234 又可以拆分为反转 12 与 34,反转 5678 拆分为反转 56 与 78。对于 12 这种长度为 2 的情况,交换 1 和 2 即完成反转。
也就是说,反转一个长度为 W 的位串,等价于「递归反转两半 + 交换两半」;这个模式本身并不新鲜,关键在于下文的加速手段。
二、利用位运算「并行计算」:自底向上合并
递归的「递」过程没有加速价值,但**「归」的过程可以并行**。190.md 巧妙地指出:去掉递归的「递」,直接看自底向上的合并。
1. 最底层:相邻两位两两交换(同时完成)
递归最底层是反转 12、34、56、78。利用位运算,这些反转可以同时完成:先把奇数位与偶数位分离,再分别移位,最后合并:
12345678
↓ 分离
1 3 5 7 (奇数位)
2 4 6 8 (偶数位)
↓ 移位
1 3 5 7
2 4 6 8
↓ 合并
21436587
2. 第二个层次:两个两个交换
在 21436587 的基础上,把相邻的 2 位块当作整体互相交换:
21436587
↓ 分离
21 65 (高两位块)
43 87 (低两位块)
↓ 移位
21 65
43 87
↓ 合并
43218765
3. 第三个层次:四个四个交换
再把相邻的 4 位块整体交换:
43218765
↓ 分离
4321 (高四位块)
8765 (低四位块)
↓ 移位
4321
8765
↓ 合并
87654321
4. 推广到 32 位
对 32 位整数,依此类推:相邻位两两交换 → 两个两个交换 → 四个四个交换 → 八个八个交换 → 最后交换高低 16 位。整个过程一共 5 轮,每一轮内部都是完全并行的位运算。
三、掩码常量与五步实现
每一轮「分离 → 移位 → 合并」需要一对互补掩码。190.md 给出的五个常量如下:
| 常量 | 十六进制 | 二进制规律 | 用途 |
|---|---|---|---|
m0 |
0x55555555 |
01010101 ... |
每 1 位交替,分离相邻位 |
m1 |
0x33333333 |
00110011 ... |
每 2 位一组交替 |
m2 |
0x0f0f0f0f |
00001111 ... |
每 4 位一组交替 |
m3 |
0x00ff00ff |
00000000111111110000000011111111 |
每 8 位一组交替 |
m4 |
0x0000ffff |
低 16 位全 1 | 分离高低 16 位 |
注意 0x55555555 = 0b0101... 对应的十六进制每个数位是 5,0x33333333 每个数位是 3,0x0f0f0f0f 每个数位是 f,记起来很方便。
Go 实现
const m0 = 0x55555555 // 01010101 ...
const m1 = 0x33333333 // 00110011 ...
const m2 = 0x0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff // 00000000111111110000000011111111
const m4 = 0x0000ffff // 00000000000000001111111111111111
func reverseBits(n int) int {
n = n>>1&m0 | n&m0<<1 // 交换相邻位
n = n>>2&m1 | n&m1<<2 // 两个两个交换
n = n>>4&m2 | n&m2<<4 // 四个四个交换
n = n>>8&m3 | n&m3<<8 // 八个八个交换
return n>>16 | n&m4<<16 // 交换高低 16 位
}
每一行的语义都是对称的:n >> k & mask 取出右移后的部分,n & mask << k 取出左移前的部分,两者按位或合并,就完成了「块级交换」。以第一行为例,n>>1&m0 把偶数位(右移后落在奇数位上的原偶数位)保留,n&m0<<1 把奇数位左移一格,两者合并后相邻位互换。
Python 实现
m0 = 0x55555555 # 01010101 ...
m1 = 0x33333333 # 00110011 ...
m2 = 0x0f0f0f0f # 00001111 ...
m3 = 0x00ff00ff # 00000000111111110000000011111111
m4 = 0x0000ffff # 00000000000000001111111111111111
class Solution:
def reverseBits(self, n: int) -> int:
n = n>>1&m0 | (n&m0)<<1 # 交换相邻位
n = n>>2&m1 | (n&m1)<<2 # 两个两个交换
n = n>>4&m2 | (n&m2)<<4 # 四个四个交换
n = n>>8&m3 | (n&m3)<<8 # 八个八个交换
return n>>16 | (n&m4)<<16 # 交换高低 16 位
Java 实现
Java 的 int 是有符号 32 位整数,右移必须使用无符号右移 >>>,避免符号位扩散:
class Solution {
private static final int m0 = 0x55555555; // 01010101 ...
private static final int m1 = 0x33333333; // 00110011 ...
private static final int m2 = 0x0f0f0f0f; // 00001111 ...
private static final int m3 = 0x00ff00ff; // 00000000111111110000000011111111
public int reverseBits(int n) {
n = n>>>1&m0 | (n&m0)<<1; // 交换相邻位
n = n>>>2&m1 | (n&m1)<<2; // 两个两个交换
n = n>>>4&m2 | (n&m2)<<4; // 四个四个交换
n = n>>>8&m3 | (n&m3)<<8; // 八个八个交换
return n>>>16 | n<<16; // 交换高低 16 位
}
}
C++ 实现
C++ 侧用 uint32_t 显式声明掩码常量与内部函数,避免符号位问题:
class Solution {
static constexpr uint32_t m0 = 0x55555555; // 01010101 ...
static constexpr uint32_t m1 = 0x33333333; // 00110011 ...
static constexpr uint32_t m2 = 0x0f0f0f0f; // 00001111 ...
static constexpr uint32_t m3 = 0x00ff00ff; // 00000000111111110000000011111111
uint32_t reverseBits32(uint32_t n) {
n = n>>1&m0 | (n&m0)<<1; // 交换相邻位
n = n>>2&m1 | (n&m1)<<2; // 两个两个交换
n = n>>4&m2 | (n&m2)<<4; // 四个四个交换
n = n>>8&m3 | (n&m3)<<8; // 八个八个交换
return n>>16 | n<<16; // 交换高低 16 位
}
public:
int reverseBits(int n) {
return reverseBits32(n);
}
};
四、复杂度分析
- 时间复杂度:O(1)。无论输入是
0还是2^31 - 2,计算量没有任何区别。更精细地说,时间复杂度是 O(log W),其中 W = 32 是位宽:每轮把块的大小翻倍,共 log₂32 = 5 轮。 - 空间复杂度:O(1)。只使用常数个掩码常量与临时变量,不随输入规模增长。
这也是「分治 + 位运算并行」相比逐位循环(O(W))的核心优势:把 W 次串行操作压缩成 log W 轮并行操作,每轮只需要常数条指令。
五、附:库函数写法
竞赛或工程实践中,也可以直接调用语言内置能力,代码更短但一般不再体现分治原理:
class Solution:
def reverseBits(self, n: int) -> int:
# 没有 O(1) 的库函数,只能用字符串转换代替
# 032b 中的 b 表示转成二进制串,032 表示补前导零到长度等于 32
return int(f'{n:032b}'[::-1], 2)
Python 没有 O(1) 的位反转库函数,因此用格式化二进制字符串 f'{n:032b}'(032 补前导零到 32 位,b 表示二进制)再反转、再转回整数;也可以等价写成 int(bin(n)[2:].zfill(32)[::-1], 2)。
class Solution {
public int reverseBits(int n) {
return Integer.reverse(n);
}
}
class Solution {
public:
int reverseBits(int n) {
return __builtin_bitreverse32(n);
}
};
func reverseBits(n int) int {
return int(bits.Reverse32(uint32(n)))
}
其中 Go 版本直接调用标准库 math/bits 的 bits.Reverse32,与本仓库 copypasta/bits.go 中「标准库 math/bits 包含位运算常用函数」的说明一致——像二进制中 1 的个数、二进制表示长度、位反转这类原子操作,竞赛模板与工程代码都推荐优先复用标准库。
六、仓库内的延伸:从 LC190 到竞赛题目
这套「按位块交换」的递归思维不止解决 LC190,它在本仓库中被多次引用:
- copypasta/bits.go 是仓库的位运算模板集合,开头注释就整理了大量位运算技巧分类与题单,涉及与或(AND/OR)区间求和单调性、异或(XOR)性质、lowbit、拆位贡献法等,并提示「有关二进制枚举、枚举子集的子集等写法,见 search.go」,与本仓库 copypasta/search.go 相互印证。
- copypasta/segment_tree.go 的注释(约 L56 附近)在 CF1401F(2400 分,「区间 swap & reverse」)处明确写道「联想 reverse bit 的递归思路」。这说明:线段树上维护「区间内元素整体反转」这类操作时,同样可以把区间按 2 的幂分层,用类似的反转/交换标记自顶向下或自底向上合并,与 LC190 的掩码法同源。
也就是说,理解 LC190 的价值在于掌握一种通用的分层交换模式:任何「把整个序列/位串按位序颠倒」的需求,都可以考虑先按最小粒度交换、再逐层扩大块的大小,配合位掩码实现 O(1)(或 O(log W))的并行完成。
小结
- 反转 32 位二进制整数 = 5 轮「分离 → 移位 → 合并」,每轮用一对互补掩码(
m0~m4)并行交换不同粒度的位块。 - 时间复杂度 O(1)(更精细地讲 O(log W)),空间复杂度 O(1),远优于逐位循环。
- 实战中可改用库函数:Java
Integer.reverse、C++__builtin_bitreverse32、Gobits.Reverse32;Python 无 O(1) 库函数,退而使用032b格式化字符串。 - 该分治思维在本仓库中延伸到线段树区间 swap & reverse(CF1401F)等高级题目,属于可复用的位运算模板思想。
</|DSML|parameter> </|DSML|invoke> </|DSML|tool_calls>