1

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

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

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

4

2 回答 2

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;
}

PS这里是根据描述更改修改的代码：

#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;
}
于 2013-03-07T10:35:16.347 回答
0

如果您只想更改数字 N 中的两位，可以使用以下命令：

for (size_t i = 0; i < sizeof(int); ++i) {
    int one = N ^ (1<<i);
    for (size_t j = 0; j < i; ++j)
        vec.push(one ^ (1<<j));
    vec.push(one);
}
vec.push(N);

对于任何另一个 n：生成一个数字列表，其中设置了 n、(n-1)、... 0 位，并将您的 N 与所有这些位进行异或。有很多已回答的问题，如何生成这样的列表。事实上，对于大 n，有 O(2^(sizeof(int))) 个可能的数字。如果我只想迭代它们，我更喜欢使用生成器，而不是完整列表。

于 2013-03-07T08:39:06.927 回答