C++中高效生成整数二进制表示子集的算法需求

这个问题我之前也碰到过，其实核心就是只聚焦N二进制里的1的位置来生成子集，完全不用遍历所有小于N的数，哪怕N是超大整数也能高效处理。

核心思路拆解 #

首先要明确：“二进制表示是N的子集”其实就是只保留N二进制中部分1的位置，其余位全为0。比如N=52（二进制110100），里面的1在第2、4、5位（从0开始计数），对应的权值是2^2=4、2^4=16、2^5=32。我们要做的就是生成这些权值的所有非空组合，把组合里的数加起来就是目标整数。

这个思路的优势在于：我们只需要处理N中1的个数k，生成的子集数是2^k - 1，如果N的汉明重量k不大（比如k≤20，子集数才100多万），效率极高；即使k稍大，这也是理论上的最优解——因为你本来就需要生成这么多个数，不可能有比枚举所有子集更快的方法。

C++实现步骤 #

第一步：提取N中所有1的权值

先遍历N的二进制位，把每个1对应的权值（2^pos）存起来：

#include <vector>
#include <cstdint> // 处理大整数用

std::vector<uint64_t> extract_set_bits(uint64_t N) {
    std::vector<uint64_t> bit_weights;
    int pos = 0;
    while (N > 0) {
        if (N & 1) {
            bit_weights.push_back(1ULL << pos); // 用ULL避免移位溢出
        }
        N >>= 1;
        pos++;
    }
    return bit_weights;
}

第二步：枚举所有非空子集生成目标数

用位掩码枚举每个子集：掩码的每一位对应是否选择对应的权值，把选中的权值相加就是结果。

std::vector<uint64_t> generate_subset_integers(uint64_t N) {
    auto bit_weights = extract_set_bits(N);
    int k = bit_weights.size();
    std::vector<uint64_t> result;
    result.reserve((1ULL << k) - 1); // 预分配内存，避免频繁扩容

    // 枚举所有非空子集，掩码从1到(1<<k)-1
    for (uint64_t mask = 1; mask < (1ULL << k); ++mask) {
        uint64_t num = 0;
        for (int i = 0; i < k; ++i) {
            if (mask & (1ULL << i)) {
                num += bit_weights[i];
            }
        }
        result.push_back(num);
    }
    return result;
}

测试示例 #

拿你给的N=52测试：

#include <iostream>
int main() {
    uint64_t N = 52;
    auto nums = generate_subset_integers(N);
    for (auto num : nums) {
        std::cout << num << " ";
    }
    // 输出：4 16 20 32 36 48，和预期完全一致
    return 0;
}

额外优化说明 #

• 如果N是32位整数，把uint64_t换成int或者uint32_t就行，不影响逻辑。
• 如果你需要包含0（空子集），只需要把掩码的起始值改成0，同时调整reserve的大小为1<<k。
• 对于汉明重量k很大的情况（比如k=30，子集数超过10亿），这个方法依然是最优的，但此时生成这么多数的本身就会占用大量内存和时间，这是问题本身的性质决定的，没有更优的办法。

内容的提问来源于stack exchange，提问作者Fedor Šimkovic