La creazione di più numeri con certo numero di bit impostati

Question

Problema

Ho bisogno di creare 32 numeri bit (con o senza segno non importa, il bit massima sarà mai essere impostato in ogni caso) e ogni numero deve avere un certo numero di bit impostato.

Soluzione Naive

La soluzione più semplice è ovviamente quello di iniziare con il numero di zero. All'interno di un ciclo il numero è ora aumentato di uno, il numero di bit viene contato, se il conteggio ha il valore desiderato, il numero viene memorizzato in una lista, se non il ciclo si ripete solo. Il ciclo si arresta se sono stati trovati abbastanza numeri. Naturalmente questo funziona bene, ma è terribilmente lento una volta che il numero di bit desiderato diventa molto alta.

Una soluzione migliore

Il numero più semplice avere (diciamo) 5 bit impostati è il numero in cui sono impostati i primi 5 bit. Questo numero può essere facilmente creato. All'interno di un ciclo il primo bit è impostato e il numero è spostato a sinistra di uno. Questo ciclo viene eseguito 5 volte e ho trovato il primo numero con 5 bit impostati. Il prossimo paio di numeri sono facili da creare pure. Ora pretendiamo che il numero sia 6 bit di larghezza e la più alta non è impostato. Ora si comincia spostando il primo bit zero a destra, in modo da ottenere 101111, 110111, 111011, 111101, 111110. Potremmo ripetere questo con l'aggiunta di un altro 0 a fronte e ripetendo questo processo. 0111110, 1011110, 1101110, ecc, tuttavia in questo modo i numeri cresceranno molto più velocemente del necessario, come utilizzare questo approccio semplice lasciamo i numeri come 1.010.111.

Così, c'è un modo migliore per creare tutte le possibili permutazioni, un approccio generico, che può essere utilizzato, a prescindere quanti bit il numero successivo avrà e indipendentemente da quanti bit insieme abbiamo bisogno di set?

Answer 1

È possibile utilizzare il bit-giocherellando incidere da hackersdelight.org .

Nel suo libro che ha il codice per ottenere il numero successivo più alto con lo stesso numero di serie di un bit.

Se si utilizza questo come un primitivo per aumentare il numero di tutto ciò che dovete fare è trovare un punto di partenza. Come il primo numero di N bit impostati è facile. E 'solo 2 ^ (N-1) -1.

Si scorrere tutti i numeri possibili molto veloce in questo modo.

  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

Prova affrontare il problema dal modo opposto rotondo -. Quello che stai cercando di fare è equivalente a "trovare n i numeri nel range 0-31"

Supponiamo che si sta cercando di trovare 4 numeri. Si inizia con [0,1,2,3] e quindi aumentare l'ultimo numero ogni volta (sempre [0,1,2,4], [0,1,2,5] ...) fino a colpire il limite [0,1,2,31]. Quindi aumentare il numero penultima, e impostare l'ultimo numero a uno più alto: [0,1,3,4]. Torna ad aumentare l'ultimo numero: [0,1,3,5], [0,1,3,6] ... ecc Una volta che si ha colpito alla fine di questo, si torna a [0,1,4 , 5] - alla fine si raggiunge [0,1,30,31] a questo punto si deve fare marcia indietro un passo in più: [0,2,3,4] e il gioco è fatto di nuovo. Continuate fino a quando finalmente finisce con [28,29,30,31].

Dato un insieme di numeri, è ovviamente facile per convertirli in numeri a 32 bit.

Answer 3

Si desidera generare combinazioni, vedere questo Wikipedia articolo .

Answer 4

Si sia bisogno di permutazioni Factoradic (Google su questo) o uno di algoritmi su Wiki