如何用C++高效生成两个二进制数的不同位组合数？

核心思路很清晰：先通过XOR定位两个数的不同位，再遍历这些位的所有可能组合，将组合与两个数的公共位合并，得到所有目标数字。

关键步骤拆解 #

1. 定位不同位：对两个数执行XOR操作，得到的结果mask中，所有二进制位为1的位置就是两个数的不同位。比如5(101)和3(011)的XOR结果是6(110)，说明第1、2位（从0开始计数）是不同位。
2. 统计不同位数量：通过位计数函数得到mask中1的个数count，总组合数就是2^count。
3. 遍历所有组合：枚举mask的所有子掩码（即不同位的所有可能组合），将子掩码与两个数的公共位合并，生成每个目标数字。

高效实现代码 #

方法一：枚举子掩码（最优性能） #

利用位运算直接遍历mask的所有子掩码，无需额外存储位位置，效率最高：

#include <iostream>
#include <bitset>

using namespace std;

void generateAllCombinations(int num1, int num2) {
    unsigned int mask = num1 ^ num2;
    unsigned int common_bits = num1 & ~mask; // 两个数相同的位
    
    unsigned int submask = mask;
    do {
        unsigned int result = common_bits | submask;
        cout << result << " (" << bitset<3>(result) << ")" << endl;
        submask = (submask - 1) & mask;
    } while (submask != mask); // 循环直到回到初始mask，完成所有子掩码遍历
}

int main() {
    generateAllCombinations(5, 3);
    return 0;
}

运行输出：

7 (111)
5 (101)
3 (011)
1 (001)

原理：(submask - 1) & mask是枚举子掩码的经典技巧，每次迭代都会生成一个新的子掩码，直到遍历完所有可能。

方法二：位映射枚举（更易理解） #

先提取mask中所有置位的位置，再通过枚举0到2^count-1来映射生成子掩码，适合新手理解：

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

using namespace std;

vector<int> generateAllCombinations(int num1, int num2) {
    int mask = num1 ^ num2;
    vector<int> diff_bits;
    // 提取所有不同位的位置
    for (int i = 0; i < sizeof(int) * 8; ++i) {
        if (mask & (1 << i)) {
            diff_bits.push_back(i);
        }
    }
    
    int total = 1 << diff_bits.size();
    vector<int> results;
    results.reserve(total);
    
    // 枚举所有组合
    for (int i = 0; i < total; ++i) {
        int submask = 0;
        for (int j = 0; j < diff_bits.size(); ++j) {
            if (i & (1 << j)) {
                submask |= (1 << diff_bits[j]);
            }
        }
        results.push_back( (num1 & ~mask) | submask );
    }
    return results;
}

int main() {
    vector<int> res = generateAllCombinations(5, 3);
    for (int num : res) {
        cout << num << " (" << bitset<3>(num) << ")" << endl;
    }
    return 0;
}

性能说明 #

两种方法的时间复杂度都是O(2^count)，这是理论最优复杂度——因为必须生成2^count个结果。其他操作（XOR、位计数、子掩码枚举）都是常数时间或固定位数的线性时间，性能可以忽略不计。

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