algorithm - 如何生成对二进制整数的所有有效位变化的组合？

Question

定义一个 2 位或更少的向 32 位整数的变化被认为是“有效的”。
为简化起见，我们以 4 位二进制为例。
0000 -> 1000 有效
0000 -> 1100 有效
0000 -> 1001 有效
0000 -> 1101 无效

所以实际上这意味着有 C(32, 2) * 2^2 种可能的组合

我想知道如何编写像 vector<int> foo(int numberToBeChanged, int n) 这样的函数这需要一个数字 n (允许的位更改数)并返回所有可能组合的集合？谢谢。

Answer 1

这样做就可以了:

#include <iostream>
#include <vector>
using namespace std;

vector<unsigned int> foo(unsigned int n)
{
    vector<unsigned int> ans;

    // One of the combinations is not to change anything, i.e. number itself
    ans.push_back(n);

    for(unsigned int i = 0; i < 32; i++) {
        // Combinations with only one bit changed
        ans.push_back(n ^ (1 << i));
        for(unsigned int j = 0; j < i; j++) {
            // Combinations with two bits changed
            ans.push_back(n ^ (1 << i) ^ (1 << j));
        }
    }
    return ans;
}

int main()
{
    vector<unsigned int> v = foo(0);
    for(unsigned int i = 0; i < v.size(); i++) {
        cout << v[i] << endl;
    }
    return 0;
}

附言 这是根据描述更改修改后的代码:

#include <iostream>
#include <vector>
using namespace std;

/*
    start denotes bit number from which we should start loop, i.e. we can't
    modify any bits before that bit to avoid duplicates (we are modifying bits
    with order from lowest to highest, so if we have modified some bit, next bit
    to modify should be a higher one.
*/
void foo(vector<unsigned int>& ans, unsigned int number, int n, unsigned int start)
{
    // As we reached to current number someway then it is one of the combinations
    ans.push_back(number);
    if(n < 1) {
        // No more changes allowed, go back
        return;
    }

    // Try change one bit
    for(unsigned int i = start; i < 32; i++) {
        foo(ans, number ^ (1 << i), n - 1, i + 1);
    }
}

int main()
{
    vector<unsigned int> v;
    unsigned int startingNumber = 0;
    int changesAllowed = 2;
    foo(v, startingNumber, changesAllowed, 0);
    for(unsigned int i = 0; i < v.size(); i++) {
        cout << v[i] << endl;
    }
    return 0;
}