基于C++的递归算法实现位掩码组合生成问题求助

解决方案思路 #

核心逻辑是递归遍历每个掩码的所有可能取值，逐步叠加组合结果：

• 递归函数跟踪当前处理的掩码索引、已生成的组合值；
• 对每个掩码，遍历0到对应上限的所有数值，计算该数值对应的位段值（匹配掩码的位位置）；
• 递归处理下一个掩码，当所有掩码处理完成时，将最终组合值存入结果集合。

完整实现代码 #

#include <vector>
#include <cstdint>
#include <iostream>
#include <bitset>

// 跨平台实现计算尾随零的个数（替代GCC内置的__builtin_ctz）
int countTrailingZeros(uint32_t mask) {
    if (mask == 0) return 32;
    int cnt = 0;
    while ((mask & 1) == 0) {
        cnt++;
        mask >>= 1;
    }
    return cnt;
}

void generateCombinations(int index, uint32_t currentValue, 
                          const std::vector<uint32_t>& masks, 
                          const std::vector<int>& limits, 
                          std::vector<uint32_t>& results) {
    // 递归终止：所有掩码处理完毕，保存当前组合值
    if (index == masks.size()) {
        results.push_back(currentValue);
        return;
    }

    const uint32_t mask = masks[index];
    const int limit = limits[index];

    // 计算掩码的最低位偏移，以及位段的单位值
    const int shift = countTrailingZeros(mask);
    const uint32_t unit = mask / __builtin_popcount(mask); // 假设掩码是连续位段

    // 遍历当前掩码的所有可能取值
    for (int val = 0; val <= limit; ++val) {
        const uint32_t segmentValue = static_cast<uint32_t>(val) * unit;
        // 递归处理下一个掩码，叠加当前位段值
        generateCombinations(index + 1, currentValue | segmentValue, masks, limits, results);
    }
}

int main() {
    // 测试示例1：掩码[0x10, 0x01]，上限[2,4]
    std::vector<uint32_t> masks1 = {0x10, 0x01};
    std::vector<int> limits1 = {2, 4};
    std::vector<uint32_t> results1;
    generateCombinations(0, 0, masks1, limits1, results1);

    std::cout << "示例1结果（共" << results1.size() << "个）：\n";
    for (uint32_t val : results1) {
        std::cout << "0x" << std::hex << val << std::dec 
                  << " (" << std::bitset<8>(val) << ")\n";
    }

    // 测试示例2：掩码[0x100, 0x010, 0x001]，上限[2,3,2]
    std::vector<uint32_t> masks2 = {0x100, 0x010, 0x001};
    std::vector<int> limits2 = {2, 3, 2};
    std::vector<uint32_t> results2;
    generateCombinations(0, 0, masks2, limits2, results2);

    std::cout << "\n示例2结果（共" << results2.size() << "个）：\n";
    for (uint32_t val : results2) {
        std::cout << "0x" << std::hex << val << std::dec 
                  << " (" << std::bitset<16>(val) << ")\n";
    }

    return 0;
}

关键细节说明 #

1. 位段计算：
   • countTrailingZeros用于确定掩码的最低位位置，保证数值能正确映射到掩码对应的位区域；
   • unit是掩码位段的最小单位（比如掩码0x30对应两位，单位是0x10），确保取值val能生成合法的位段值。
2. 递归逻辑：
   • 每次递归只处理一个掩码，遍历其所有可能取值后，传递叠加后的组合值给下一层递归；
   • 终止条件为所有掩码处理完成，此时的currentValue就是一个完整的组合结果。
3. 输入约束：
   • 请确保输入的掩码是互不重叠的连续位段（如0x0F、0x30）或单个位（如0x01、0x10），否则可能生成不符合预期的位段值。

内容的提问来源于stack exchange，提问作者devg1