codeforces-go 位运算实战:LeetCode 190 反转二进制位的分治与并行掩码法

原创2026-10-08 19:05:331,764 阅读
文章标签:开发工具

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。分治的思考路径分三步:

  1. 递归反转左半 1234,得到 4321;
  2. 递归反转右半 5678,得到 8765;
  3. 交换 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、Go bits.Reverse32;Python 无 O(1) 库函数,退而使用 032b 格式化字符串。
  • 该分治思维在本仓库中延伸到线段树区间 swap & reverse(CF1401F)等高级题目,属于可复用的位运算模板思想。

</|DSML|parameter> </|DSML|invoke> </|DSML|tool_calls>

登录后查看全文
codeforces-go