設定されたビットの特定の数の複数の番号を作成します

Question

問題

私は（最上位ビットがとにかく設定されることはありません、問題ではありません符号付きまたは符号なし）と各番号はビットセットの与えられた数を持っている必要があります32ビット番号を作成する必要があります。

ナイーブソリューション

最も簡単な解決策は、ゼロの数で開始することは勿論です。ループ内の数は現在1だけ増加され、ビット数がカウントされるカウント値が所望の値を有する場合ではないループだけ繰り返される場合、数は、リストに格納されています。十分な数が発見された場合はループが停止しています。もちろん、これはうまく動作しますが、希望のビット数が非常に高くなったら、それはとても遅いです。

Aよりよい解決策

5ビットが設定（のは言わせて）を有する最も単純な数は、第5ビットが設定されている数です。この数は、簡単に作成することができます。ループ内の最初のビットがセットされ、数は、一つだけ左にシフトします。このループは5回実行され、私は設定5ビットと最初の番号を見つけました。数字の次のカップルは、同様に簡単に作成できます。私たちは今、数は6ビット幅と最高の1が設定されていないふりをします。今、私たちは右に最初のゼロビットをシフトし始めるので、我々は我々が前に別の0を追加し、このプロセスを繰り返すことによって、これを繰り返すことができ101111、110111、111011、111101、111110.を取得します。 0111110、1011110、1101110、などしかし、そのように番号が、我々は1010111のような数字を残して、この単純なアプローチを使用して、必要以上にはるかに速く成長します。

だから、次の番号は、我々が設定する必要がどのように多くのセットのビットにかかわらず、持っているとされますどのように多くのビット？かかわらず、使用可能なすべての順列を作成するためのより良い方法、一般的なアプローチがある。

Answer 1

あなたは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);
    }
  }

Answer 2

ラウンド反対方向から問題にアプローチしてみ - あなたが何をしようとしていることは、「範囲0-31で見つけるのN の数字」と同等です。

。

あなたは4つの番号を検索しようとしていると仮定します。あなたは[0,1,2,3]で始まり、その後、あなたが限界に達しまで、各時間（[0,1,2,4]取得、[0,1,2,5] ...）最後の数を増やします[0,1,2,31]。そして、最後から二番目の数を増やし、より高いものに最後の番号を設定：[0,1,3,4]。最後の数を増やすに戻る：あなたはこの年末にヒットしたら、[0,1,3,5]、[0,1,3,6] ...など、あなたが[0,1,4に戻ります、5] - 最終的にはあなたが届く[0,1,30,31]これであなたはさらに一歩後戻りしなければならないポイント：[0,2,3,4]とあなたがもう一度行くオフ。あなたが最後に[28,29,30,31]で終わるまで続ける。

数の集合を考えると、これは32ビットの数値に変換することは明らかに簡単です。

Answer 3

あなたは組み合わせを生成したい、この Wikipediaの記事を参照してください。

Answer 4

あなたはウィキ