9

unsigned f(unsigned)に設定されたビット数が でf(i)増加するiか、少なくとも減少しない可逆関数を探しています。明らかに、そのときf(0)は 0 でなければならず、f(~0) は最後に来なければなりません。その間に柔軟性があります。f(0) の後、次の 32* の値は1U<<0to1U<<31でなければなりませんが、順序についてはあまり気にしません (すべて 1 ビットが設定されています)。

f(0)...f(i-1)を計算するために計算する必要のないアルゴリズムがf(i)欲しいのですが、完全なテーブルも機能しません。

これはグレイ コードに似ていますが、そのアルゴリズムを再利用する方法がわかりません。これを使用して大規模なデータセットにラベルを付け、それらを検索する順序に優先順位を付けようとしています。アイデアは、私が鍵を持っているということで、CラベルをチェックしC ^ f(i)ます。の値が小さいと、 にi似たラベルが表示されるはずですC。つまり、わずか数ビットだけ異なります。

unsigned[*] 32 ビットであると想定しないことに対するボーナス ポイント。

[例] 有効な初期シーケンス:

0, 1, 2, 4, 16, 8 ... // 16 and 8 both have one bit set, so they compare equal

無効な初期シーケンス:

0, 1, 2, 3, 4 ... // 3 has two bits set, so it cannot precede 4 or 2147483648.
4

2 に答える 2

2

わかりました、私は合理的な答えを持っているようです。まず、ビットからbinom(n,k)設定できる方法の数として定義しましょう。これが古典的なパスカルの三角形です。kn

1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1
...

簡単に計算してキャッシュします。各行の合計は であることに注意してください1<<lineNumber。

次に必要なのは、partial_sumその三角形の です。

1  2
1  3  4
1  4  7  8
1  5 11 15 16
1  6 16 26 31  32
1  7 22 42 57  63  64
1  8 29 64 99  120 127 128
1  9 37 93 163 219 247 255 256 
...

繰り返しますが、このテーブルは前の行の 2 つの値を合計することで作成できますが、各行の新しいエントリは1<<lineではなく1.

上記のこれらの表を使用して、8 ビットの数値を作成してみましょうf(x)(任意のビット数に簡単に一般化できます)。f(0)最初の三角形の 8 番目の行を見上げると、次の 8 つのエントリがf(1)でf(9)あり、すべて 1 ビットが設定されていることがわかります。次の 28 エントリ (7+6+5+4+3+2+1) にはすべて 2 ビットが設定されているため、f(10) から f(37) になります。次の 56 エントリ f(38) ～ f(93) は 3 ビットで、4 ビットが設定された 70 エントリがあります。対称性から、それらは f(128) を中心に、特に f(94) から f(163) にあることがわかります。そして明らかに、8 ビットが設定された唯一の数値は、f(255) として最後に並べ替えられます。

したがって、これらの表を使用して、f(i) に設定する必要があるビット数をすばやく判断できます。テーブルの最後の行でバイナリ検索を実行するだけです。しかし、どのビットが設定されているかは正確にはわかりません。そのためには、前の行が必要です。

テーブルの各値が前の行から作成できる理由は簡単です。binom(n,k) == binom(k, n-1) + binom(k-1, n-1)。0...k ビットが設定された数値には、aで始まる数値と で始まる数値の 2 種類があります1...。最初のケースでは、次のn-1ビットにこれらのビットが含まれている必要がありk、2 番目のケースでは、次のn-1ビットにビットのみが含まれている必要がありk-1ます。特殊なケースはもちろん0 out of nとn out of n.

これと同じ構造を使用して、何が必要かをすばやく伝えることができf(16)ます。範囲内にあるため、2 ビット セットが含まれている必要があることは既に確認済みですf(10) - f(37)。特に、2 ビットが設定された 6 番です (通常どおり 0 から始まります)。この範囲の長さを 28 から 1 に縮小しようとするため、これを範囲内のオフセットとして定義すると便利です。

その範囲を、0 で始まる 21 個の値と 1 で始まる 7 個の値に分割します。6 < 21 なので、最初の桁がゼロであることがわかります。残りの 7 ビットのうち、まだ 2 ビットを設定する必要があるため、三角形の 1 行上に移動すると、15 個の値が 2 つのゼロで始まり、6 個が 01 で始まることがわかります。6 < 15 であるため、f(16) は 00 で始まります。 . さらに上に行くと、 7 <= 10 なので、 で始まり000ます。0000でも 6 == 6 なのでbutで始まらない0001。この時点で、範囲の開始を変更するため、新しいオフセットは 0 (6-6) になります。

必要性は で始まり、0001余分なビットが 1 つある数字のみに注目できることがわかっていますf(16)...f(19)。範囲が であることを知っていれば明らかですf(16)=00010001, f(17)=00010010, f(18)=00010100, f(19)=00011000。

したがって、各ビットを計算するには、三角形の 1 行を上に移動し、「剰余」を比較し、比較に基づいて 0 または 1 を追加して、1 列左に移動します。つまり、 の計算量f(x)はO(bits)、またはO(log N)であり、必要なストレージは ですO(bits*bits)。

于 2013-10-11T09:16:15.430 に答える
1

与えられた数値ごとに、正確に値が 1 のビットを持つビット整数がkあることがわかっています。これで、ビット数が 1 未満の数をそれぞれ格納する整数のルックアップ テーブルを生成できます。このルックアップ テーブルを使用して、の 1 ビットの数を見つけることができます。binom(n, k) nkn + 1kof(i)

この数がわかったら、このビット数のルックアップ テーブル値を減算します。そこから、指定された数の 1 ビットを持つ数iの順列インデックスが得られます。p私はこの分野で調査を行っていませんが、最下位ビットのstd::vector<bool>ゼロと 1 で初期化された a の p 番目の順列を見つける方法が存在することは確かです。o

逆関数

ここでも、ルックアップ テーブルが役立ちます。入力整数の 1 ビットをカウントし、ルックアップ テーブルを読み取ることで、先行する 1 ビット未満の数値の数を直接計算できます。次に、順列インデックスを決定し、それを検索値に追加するだけで済みます。

免責事項

もちろん、これは大まかな概要に過ぎず、いくつかの部分 (特に順列を含む) は思ったよりも長くかかる場合があります。

添加

あなたは自分自身を述べました

これを使用して大規模なデータセットにラベルを付け、それらを検索する順序に優先順位を付けようとしています。

これは、低ハミング距離から高ハミング距離に移行するかのように聞こえます。この場合、前の番号から次の番号を生成する増分バージョンがあれば十分です。

unsigned next(unsigned previous)
{
    if(std::next_permutation(previous))
        return previous;
    else
        return (1 << (1 + countOneBits(previous))) - 1;
}

もちろんstd::next_permutation、順列はこのようには機能しませんが、それをどのように使用するつもりかは明らかだと思います。

于 2013-10-10T14:26:37.827 に答える