20

問題

32ビットの数値を作成する必要があり（符号付きか符号なしかは関係ありません。とにかく最上位ビットが設定されることはありません）、各数値には特定の数のビットが設定されている必要があります。

素朴な解決策

もちろん、最も簡単な解決策はゼロから始めることです。ループ内では、数値が 1 ずつ増加し、ビット数がカウントされます。カウントが目的の値である場合、数値がリストに格納されます。そうでない場合は、ループが繰り返されます。十分な数が見つかった場合、ループは停止します。もちろん、これは問題なく動作しますが、必要なビット数が非常に多くなると、非常に遅くなります。

より良いソリューション

(たとえば) 5 ビットが設定されている最も単純な数値は、最初の 5 ビットが設定されている数値です。この番号は簡単に作成できます。ループ内で最初のビットが設定され、数値が 1 つ左にシフトされます。このループは 5 回実行され、5 ビットが設定された最初の数値が見つかりました。次の数も簡単に作成できます。ここで、数値が 6 ビット幅であると仮定し、最高の数値は設定されていません。ここで、最初の 0 ビットを右にシフトし始め、101111、110111、111011、111101、111110 を取得します。前に別の 0 を追加してこのプロセスを繰り返すことで、これを繰り返すことができます。0111110、1011110、1101110 など。ただし、この単純なアプローチを使用すると、1010111 などの数字が除外されるため、数字が必要以上に速く成長します。

次の数値のビット数に関係なく、設定する必要があるビット数に関係なく、使用できるすべての可能な順列、一般的なアプローチを作成するより良い方法はありますか?

4

4 に答える 4

17

hackersdelight.orgのビットいじりハックを使用できます。

彼の著書には、同じ数の 1 ビット セットで次に高い数を取得するコードがあります。

これをプリミティブとして使用して数を増やす場合、必要なのは開始点を見つけることだけです。N ビットが設定された最初の数値を取得するのは簡単です。ちょうど 2^(N-1) -1 です。

そのようにして、可能なすべての数値を非常に高速に反復処理します。

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;
   
     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }
于 2009-02-03T12:11:18.340 に答える
15

逆の方法で問題にアプローチしてみてください。あなたがやろうとしていることは、「0-31 の範囲でn 個の数字を見つける」ことと同じです。

4 つの数字を見つけようとしているとします。[0,1,2,3] から始めて、制限に達するまで毎回最後の数値を増やします ([0,1,2,4]、[0,1,2,5] ... を取得)。 [0,1,2,31]。次に、最後から 2 番目の数字を増やし、最後の数字を 1 つ大きい [0,1,3,4] に設定します。最後の数字の増加に戻ります: [0,1,3,5]、[0,1,3,6]... など。これの終わりに達すると、[0,1,4 に戻ります。 ,5] - 最終的に [0,1,30,31] に到達した時点で、[0,2,3,4] と 1 ステップ後戻りする必要があります。最終的に [28,29,30,31] になるまで続けます。

一連の数値が与えられた場合、それらを 32 ビット数値に変換するのは明らかに簡単です。

于 2009-02-03T12:05:06.933 に答える
1

組み合わせを生成したい場合は、このウィキペディアの記事を参照してください。

于 2009-02-03T12:18:30.900 に答える
0

Factoradic Permutations (Google) またはWikiのアルゴリズムのいずれかが必要です。

于 2009-02-03T11:54:05.677 に答える