24、位操作与算法：用位运算实现子集枚举

子集枚举，说白了就是从一个集合里挑出所有可能的组合。比如你有三个元素 {a, b, c}，它的子集有：空集、{a}、{b}、{c}、{a,b}、{a,c}、{b,c}、{a,b,c}，一共 2³ = 8 个。

我早年做嵌入式开发时，经常要处理传感器组合的配置。比如一个设备有 8 个传感器，需要遍历所有可能的开启组合来测试功耗。那时候我用的就是位运算枚举法，效率极高，而且代码非常简洁。

位运算枚举的核心思想

每个元素只有两种状态：选或不选。这正好对应二进制位的 1 和 0。

假设集合有 n 个元素，我们用 n 个二进制位来表示一个子集：

• 第 i 位为 1：表示第 i 个元素被选中
• 第 i 位为 0：表示第 i 个元素未被选中

那么从 0 到 (1<

基础实现：枚举所有子集

来看一个最直接的例子。假设我们有 4 个元素，用位运算枚举所有子集：

#include <stdio.h>

void enumerate_subsets(int n) {
    int total = 1 << n;  // 2^n 个子集
    for (int mask = 0; mask < total; mask++) {
        printf("{ ");
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                printf("%d ", i);
            }
        }
        printf("}\n");
    }
}

int main() {
    enumerate_subsets(3);
    return 0;
}

输出结果：

{ }
{ 0 }
{ 1 }
{ 0 1 }
{ 2 }
{ 0 2 }
{ 1 2 }
{ 0 1 2 }

你看，代码非常短。外层循环遍历所有 mask，内层循环检查每一位是否被选中。

进阶技巧：枚举子集的子集

有时候我们需要枚举某个特定子集的所有子集。比如 mask = 0b1101，我们要找出它的所有子集。

这里有个经典技巧：

int sub = mask;
do {
    // 处理 sub
    sub = (sub - 1) & mask;
} while (sub != mask);

为什么这样能行？我解释一下：

• sub 从 mask 开始，每次减 1 后与 mask 做按位与
• 这样能跳过那些不属于 mask 的位，只保留 mask 中的位
• 当 sub 变成 0 后，再减 1 变成 -1，与 mask 按位与又回到 mask，循环结束

我曾经在一个协议解析模块里用过这个技巧。当时需要遍历某个标志位的所有子组合，用这个循环一行代码就搞定了，同事看了直呼巧妙。

实际应用：组合优化问题

子集枚举在嵌入式里最常见的场景是：从一组资源中选出最优组合。

举个例子，假设有 5 个任务，每个任务占用不同的内存和 CPU 时间，我们要找出所有能放进 64KB 内存的任务组合：

#include <stdio.h>

#define N 5
#define MEM_LIMIT 64

int mem_usage[N] = {12, 20, 8, 30, 15};

void find_feasible_subsets() {
    int total = 1 << N;
    for (int mask = 0; mask < total; mask++) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (mask & (1 << i)) {
                sum += mem_usage[i];
            }
        }
        if (sum <= MEM_LIMIT) {
            printf("可行组合: ");
            for (int i = 0; i < N; i++) {
                if (mask & (1 << i)) {
                    printf("任务%d ", i);
                }
            }
            printf("(内存: %dKB)\n", sum);
        }
    }
}

这个代码在资源受限的 MCU 上跑起来毫无压力。n 不超过 20 时，2ⁿ 次循环完全可接受。

性能对比：位运算 vs 递归

很多人习惯用递归做子集枚举。我们来对比一下：

方法	代码量	执行速度	内存占用
位运算枚举	5-10 行	极快（纯循环）	极低（几个变量）
递归回溯	15-25 行	较慢（函数调用开销）	较高（栈空间）

说白了，在嵌入式环境里，位运算几乎是碾压级的优势。没有函数调用栈，没有递归深度限制，代码还短。

SVG 流程图：子集枚举的核心逻辑

避坑指南

我踩过几个坑，写出来给大家提个醒：

• 移位溢出：当 n = 32 时，1 << 32 在 32 位系统上是未定义行为。我一般用 (1ULL << n) 来避免这个问题。
• 符号位问题：如果 mask 是 int 类型，最高位是符号位。建议用 unsigned int 来存 mask，避免意外。
• 空集处理：mask = 0 代表空集，别忘了它。有些算法会漏掉空集，导致结果不完整。

小结

位运算实现子集枚举，核心就两句话：

• 用二进制位表示元素的选择状态
• 遍历 0 到 2ⁿ-1 的所有整数

这个方法简单、高效、省内存。在嵌入式开发中，无论是做配置组合、测试用例生成，还是资源分配，都能派上用场。

嗯，今天就聊到这里。记住这个技巧，下次遇到组合枚举的问题，你也能写出让人眼前一亮的代码。

---

公众号:蓝海资料掘金营，微信deep3321