8

私の問題は次のとおりです。値xとパターンpの両方の変数が同じサイズです。目標は、p によってマスクされていないx のすべてのビット パターンを反復処理することです。

例: がある場合、 、、、および- をこの順序でp = 1001検索する必要はありません。0000000110001001

C99 の標準実装 (戻り値は、既にすべての値を返したかどうかを示します):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == mask) {
        return false;
    }
    size_t current = val & mask;
    size_t inc = 1;
    size_t new_val = current + inc;
    while ((new_val & mask) <= current) {
        inc++;
        new_val = current + inc;
    }
    *out = new_val;
    return true;
}

これをより効率的にするためのトリックが必要だと思いますが、大きな改善点を見つけることができないようです (マスクの末尾のゼロを計算し、 inc の開始値を適切に設定することを除いて、これはあまり重要ではありません)改善）。

編集：また、生成された値ごとに多くの追加作業が生成されるという事実も重要です。つまり、多くの重複が問題外であることを意味します（一部の重複は、認識できなくても問題ありません。副作用はありません仕事が終わった、それはただの減速です）。

4

3 に答える 3

16

これにより、すべてのビット パターンが逆順で生成されます ( の初期値はvalに等しい必要がありますmask)。

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == 0) {
        return false;
    }

    *out = (val - 1) & mask;
    return true;
}

そして、これ (少し分かりにくいコード) はすべてのビット パターンを直接の順序で生成します ( の初期値はval0 にする必要があります)。

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == mask) {
        return false;
    }

    *out = (val - mask) & mask;
    return true;
}
于 2013-02-03T11:49:14.917 に答える
1

あなたの例から、この疑似コードがそのトリックを行うように見えます:

current = p // set up current
getNotMasked(p, 0) // initial call


bitString current

getNotMasked(int pos)
  if (pos == current.length)
    print(current)
    return
  if (current[pos] == 1)
    current[pos] = 0
    getNotMasked(pos+1)
    current[pos] = 1
    getNotMasked(pos+1)
  else
    getNotMasked(pos+1)

ここから C コードを生成するのは難しいことではbitStringありませintん。[pos]& 1 << pos

于 2013-02-03T11:41:47.170 に答える
0

最も最適な方法は次のようになります。

  1. マスクに設定されたビットの数を数えます, p
  2. 「正規化された」バイナリ値からパターンによって決定された位置にビットをシャッフルする方法を考え出す
  3. 0..2 p -1までカウント
  4. パターン互換性のある値を生成するための各値シャッフル

もちろん、これはシャッフルの実行がかなり効率的であると想定しています。そうでない場合は、パターン内のビットの総数に応じて 0 から可能な最大値までカウントし、カウントごとにパターンを適用するだけで、ブルート フォースを実行する方が簡単です。ただし、重複の検出には少しコストがかかる場合があります。

p = 9(binary 1001 2 ) の場合、設定されるビットは 2 つだけなので、生成する値が 2 2 = 4あることがわかります。

右から 1 ビットのパターンをスキャンすると、次の「シャッフル テーブル」を作成できます。

  • ビット 0 はビット 0 からコピーされます
  • ビット 3 はビット 1 からコピーされます

したがって、0 から 3 までカウントし、各値を表に従って並べ替えることができます。

  • 00 2は出力 0000 2を与える
  • 01 2は出力 0001 2を与える
  • 10 2は出力 1000 2を与える
  • 11 2は出力 1001 2を与える
于 2013-02-03T11:39:39.257 に答える