0

タイトルと同じ質問。私は2つのアプローチを行いました。1つは簡単です。からすべてのビットマスクを生成します

2 ^ {n-1}

に

2 ^ n

そして、すべてのビットマスクについて、同じ量の1と0があるかどうかを確認し、ある場合は、それに取り組みます。そして、それが問題です。なぜなら、私はそれらを数えるだけでなく、それらのビットマスクに取り組む必要があるからです。

O（2 ^ {n / 2}）時間で実行される2番目のアプローチがありましたが、すべてのビットマスクが生成されていないようで、理由はわかりません。

2番目のアプローチは次のようなものです：0から2 ^ {n / 2}までのすべてのビットマスクを生成し、有効なビットマスク（Bと呼びます）を取得するには、次のようなことを行う必要があります：B＃〜B

ここで、〜は負です。

たとえば、n = 6なので、長さ3のビットマスクを生成します。

たとえば、私はB = 101であるため、〜Bは010になり、最終的なビットマスクは101010になります。これからわか​​るように、1と0の数は同じです。

この方法は良いですか、それとも私は何か悪いことを実装していますか？たぶん、別の興味深いアプローチが存在しますか？ありがとう

クリス

4

2 に答える 2

2

再帰的なアプローチを試してください。

void printMasks(int n0, int n1, int mask) {
    if (!n0 && !n1) {
        cerr << mask << endl;
        return;
    }
    mask <<= 1;
    if (n0) {
        printMasks(n0-1, n1, mask);
    }
    if (n1) {
        printMasks(n0, n1-1, mask | 1);
    }
}

printMasks必要な数の0と1を渡して呼び出します。たとえば、3つの1と3つの0が必要な場合は、次のように呼び出します。

printMasks(3, 3, 0);
于 2011-12-16T15:14:09.330 に答える
0

2進数が与えられると、すべてのビットを保持するのに十分な大きさのワードに対して一定数の演算を使用して、同じ数の「1」を持つ次に高い2進数を生成することができます（2の累乗による除算を想定） 1つの操作として）。

最下位の「1」（ヒント：数値をデクリメントするとどうなるか）とその上の最下位の「0」（ヒント：元の数値に「最下位の1」を追加するとどうなるか）の位置を特定します。その最下位の「0」を「1」に変更し、最下位ビットの適切な数を「1」に設定し、間にあるビットを「0」に設定する必要があります。

于 2011-12-16T21:50:12.843 に答える