Erstellen mehrerer Nummern mit bestimmten Anzahl von Bits

Question

Problem

Ich brauche 32 Bit Zahlen erstellen (mit oder ohne Vorzeichen keine Rolle spielt, wird das höchste Bit sowieso nie eingestellt werden) und jede Zahl muss eine bestimmte Anzahl von Bits gesetzt hat.

Naive Lösung

Die einfachste Lösung ist natürlich mit der Anzahl von Null zu beginnen. Innerhalb einer Schleife jetzt die Nummer um Eins erhöht wird, wird die Anzahl von Bits gezählt wird, wenn die Zählung den gewünschten Wert hat, wird die Nummer zu einer Liste gespeichert werden, wenn nicht nur die Schleife wiederholt. Die Schleife wird beendet, wenn genügend Zahlen gefunden. Natürlich funktioniert das ganz gut, aber es ist furchtbar langsam, sobald die Anzahl der gewünschten Bits sehr hoch wird.

Eine bessere Lösung

Die einfachste Zahl (sagen wir mal) 5 Bits gesetzt ist die Nummer, wo der erste 5-Bit gesetzt werden. Diese Zahl kann leicht erstellt werden. In einer Schleife wird das erste Bit gesetzt, und die Zahl wird um eins nach links verschoben. Diese Schleife läuft 5 Mal und ich fand die erste Zahl mit 5 Bits gesetzt. Die nächsten paar Zahlen sind einfach auch zu schaffen. Wir geben jetzt die Zahl sein 6 Bit breit und der höchste ist nicht gesetzt. Nun starten wir den ersten Null-Bit nach rechts verschoben werden, so dass wir 101111, 110111, 111011, 111101, 111110 Wir konnten dies wiederholen, indem Sie ein weiteren 0 bis Front hinzufügen und diesen Prozess zu wiederholen. 0111110, 1011110, 1101110, etc. Aber auf diese Weise Zahlen viel schneller als nötig wachsen werden, wie dieser einfachen Ansatz wir Zahlen auslassen wie 1.010.111.

So gibt es einen besseren Weg, um alle möglichen Permutationen zu schaffen, ein allgemeiner Ansatz, die verwendet werden können, unabhängig davon, wie viele Bits die nächste Nummer haben und unabhängig davon, wie viele gesetzten Bits setzen wir brauchen?

Answer 1

Sie können die Bit-Fummel hacken von hackersdelight.org .

In seinem Buch hat er Code, um die nächsthöhere Zahl mit der gleichen Anzahl von Ein-Bit-Satz zu erhalten.

Wenn Sie dies als eine primitive benutzen, um Ihre Zahl zu erhöhen alles, was Sie tun müssen, ist, einen Ausgangspunkt zu finden. Gibt es die erste Zahl mit N Bits ist einfach. Es ist nur 2 ^ (N-1) -1.

Sie werden durch alle möglichen Zahlen iterieren sehr schnell auf diese Weise.

  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

Versuchen Sie, das Problem aus der entgegengesetzten Art und Weise nähert Runde -. Was Sie versuchen, entspricht zu tun „finden n Zahlen im Bereich von 0 bis 31“

Angenommen, Sie versuchen, 4 Zahlen zu finden. Sie beginnen mit [0,1,2,3] und dann der letzten Zahl jedes Mal erhöhen (immer [0,1,2,4], [0,1,2,5] ...), bis Sie drücken Sie die Grenze [0,1,2,31]. Dann die vorletzte Zahl erhöhen, und stellen Sie die letzte Nummer eins höher: [0,1,3,4]. Gehen Sie zurück die letzte Nummer zur Steigerung: [0,1,3,5], [0,1,3,6] ... usw. Wenn Sie das Ende dieses treffen, gehen Sie zurück zu [0,1,4 , 5] - schließlich erreichen Sie [0,1,30,31] an welcher Stelle Sie einen Schritt weiter zurückzuverfolgen haben: [0,2,3,4] und los wieder gehen. Fahren Sie bis Sie schließlich am Ende mit [28,29,30,31].

eine Reihe von Zahlen gegeben, es ist offensichtlich leicht, sie in die 32-Bit-Zahlen zu konvertieren.

Answer 3

Sie möchten Kombinationen erzeugen, finden Sie diese Wikipedia-Artikel .

Answer 4

Sie müssen entweder Factoradic Permutationen (Google auf dem) oder einen von Algorithmen auf Wiki