Get every combination of bits for two binary numbers

For two numbers, lets say 5 (101) and 3 (011), what is the most efficient way to get every number that is a combination of the different bits in these two numbers. (i.e the solution would be 101, 011, 001, 111). The number of these is just 2^(# of bits different) which I can get from an XOR, and counting the set bits. I’m trying to do this in C++.

I tried to do an XOR and go from there, but that only tells me which bits are different, and also I don’t know how to loop through the bits to record down every combination.

>Solution :

The most concise way I can think of is this:

void find_bit_combinations(unsigned a, unsigned b) {
    for (unsigned mask = 1; mask != 0; mask <<= 1) {
        if ((a & mask) != (b & mask)) {
            find_bit_combinations(a & ~mask, b & ~mask);
            find_bit_combinations(a | mask, b | mask);
            return;
        }
    }
    std::cout << a << '\n';
}

The basic idea is that we go through all the bits from least to most significant, until there is a mismatch.
If so, we recurse, where a and b both have the same bit set or unset.
The base case is that a and b are the same, which means we have found one result.

int main() {
    find_bit_combinations(0b011, 0b101);
}

This code prints 1, 5, 3, and 7. Instead of std::cout <<, you can obviously also add the results to some container.

Further optimizations

The current code is very simple and concise, but far from optimal.
Here are some ways to improve it:

1. check initially if a == b and don’t loop if so
2. don’t start at the least significant bit, but the lowest set bit in a ^ b
   • std::countr_zero is helpful
3. don’t stop at the most significant bit, but at the greatest set bit in a ^ b
   • std::countl_zero is helpful