La creación de varios números con cierto número de conjunto de bits de

Question

Problema

Necesito crear números de 32 Bits (con o sin signo no importa, el más alto de bits nunca será el conjunto de todos modos) y cada número debe tener un número determinado de Bits.

Ingenuo Solución

La solución más fácil es, por supuesto, para iniciar con el número cero.Dentro de un bucle el número ahora es mayor a uno, el número de Bits que se cuenta, si la cuenta tiene el valor deseado, el número se almacena en una lista, si no el bucle se repite.El bucle se detiene si una cantidad suficiente de números se han encontrado.Por supuesto, esto funciona bien, pero es terriblemente lento una vez que el número de Bits deseada es muy alta.

Una Solución Mejor

El más simple número que tiene (digamos) 5 conjunto de Bits es el número donde los primeros 5 Bits se establecen.Este número puede ser creado fácilmente.Dentro de un bucle el primer bit es establecido y el número es desplazado a la izquierda por uno.Este bucle se ejecuta 5 veces y me encontré con el primer número con 5 Bits.El siguiente par de números son fáciles de crear así.Ahora podemos pretender que el número es de 6 Bits de ancho y el más alto no está configurado.Ahora podemos empezar a mover el primer bit cero a la derecha, por lo que tenemos 101111, 110111, 111011, 111101, 111110.Podemos repetir esto mediante la adición de otro 0 a frente, repitiendo este proceso.0111110, 1011110, 1101110, etc.Sin embargo, que la forma en que los números crecerán mucho más rápido de lo necesario, como el uso de este enfoque simple dejamos los números como 1010111.

Entonces, ¿hay una mejor manera de crear todas las permutaciones posibles, un enfoque genérico, que puede ser utilizado, independientemente de cuántos bits el próximo número tendrá y sin importar cuántos bits necesitamos establecer?

Answer 1

Puede utilizar el de bits haciendo girar piratear desde hackersdelight.org .

En su libro que tiene código para obtener el siguiente número más alto con el mismo número de serie de un bit.

Si utiliza esto como una primitiva para aumentar su número de todo lo que tiene que hacer es encontrar un punto de partida. Conseguir el primer número con N bits establecidos es fácil. Es sólo 2 ^ (N-1) -1.

Se le iterar a través de todos los números posibles muy rápido de esa manera.

  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

Intentar acercarse al problema desde la parte de enfrente - ¿qué estás tratando de hacer es equivalente a encontrar" n los números en el rango de 0 a 31".

Supongamos que usted está tratando de encontrar 4 números.Usted comienza con [0,1,2,3] y, a continuación, aumente el último número cada vez (llegar [0,1,2,4], [0,1,2,5] ...) hasta llegar al límite [0,1,2,31].A continuación, aumentar el penúltimo número, y establecer el último número en uno mayor:[0,1,3,4].Volver a incrementar el último número:[0,1,3,5], [0,1,3,6]...etc.Una vez que llegues al final de este, que se remontan a [0,1,4,5] - eventualmente llegar a [0,1,30,31], punto en el que usted tiene que retroceder un paso más allá:[0,2,3,4] y te vas de nuevo.Sigue adelante hasta que finalmente terminar con [28,29,30,31].

Dado un conjunto de números, es obvio que es fácil de convertir en el de 32 bits de los números.

Answer 3

Se desea generar combinaciones, consulte esta artículo de Wikipedia .

Answer 4

sea necesario permutaciones Factoradic (Google en eso) o uno de los algoritmos de Wiki