1

32 ビット整数への 2 ビット以下の変更が「有効」と見なされると定義します。
簡単にするために、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 の 2 ビットだけを変更したい場合は、次のように使用できます。

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 を xor します。そのようなリストを生成する方法など、多くの回答のある質問があります。実際、大きな n には O(2^(sizeof(int))) の可能な数があります。それらを繰り返したい場合は、完全なリストではなく、ジェネレーターを使用することをお勧めします。

于 2013-03-07T08:39:06.927 に答える