Création de plusieurs numéros avec certain nombre de bits fixés

Question

Problème

Je dois créer 32 numéros de bits (signé ou non n'a pas d'importance, le bit ne sera jamais réglé de toute façon) et chaque numéro doit avoir un certain nombre de bits défini.

Solution Naive

La solution la plus simple est bien sûr de commencer par le nombre de zéro. Au sein d'une boucle le nombre est maintenant augmenté par un, le nombre de bits est compté, si le compte a la valeur souhaitée, le numéro est enregistré à une liste, sinon la boucle se répète juste. La boucle est arrêté si le nombre suffisant ont été trouvés. Bien sûr, cela fonctionne très bien, mais il est terriblement lent une fois que le nombre de bits désiré devient très élevé.

Une meilleure solution

Le nombre le plus simple ayant (disons) 5 bits Set est le numéro où les 5 premiers bits sont réglés. Ce numéro peut être facilement créé. Au sein d'une boucle du premier bit est défini et le nombre est décalée vers la gauche par une. Cette boucle fonctionne 5 fois et je l'ai trouvé le premier numéro avec 5 bits définis. Les deux prochains numéros sont faciles à créer ainsi. Nous prétendons maintenant le nombre à 6 bits de large et le plus haut n'est pas réglé. Maintenant, nous commençons à déplacer le premier bit zéro à droite, donc nous obtenons 101111, 110111, 111011, 111101, 111110. Nous pourrions répéter cela en ajoutant un autre 0 à l'avant et répéter ce processus. 0111110, 1011110, 1101110, etc. Cependant que le nombre moyen va croître beaucoup plus rapidement que nécessaire, en utilisant cette approche simple, nous laissons des chiffres comme 1010111.

Ainsi est-il une meilleure façon de créer toutes les permutations possibles, une approche générique, qui peut être utilisé, quel que soit le nombre de bits le numéro suivant aura et quel que soit le nombre de bits ensemble nous avons besoin de définir?

Answer 1

Vous pouvez utiliser le pirater bit bidouilles de hackersdelight.org .

Dans son livre, il a le code pour obtenir le prochain nombre plus élevé avec le même nombre d'ensemble d'un bit.

Si vous utilisez cela comme une primitive pour augmenter votre nombre tout ce que vous avez à faire est de trouver un point de départ. Obtenir le premier numéro avec N bits définis est facile. Il est à seulement 2 ^ (N-1) -1.

Vous itérer tous les numéros possibles très rapidement de cette façon.

  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

Essayez de prendre le problème à l'opposé rond -. Ce que vous essayez de faire est équivalent à « trouver n nombres dans la gamme 0-31 »

Supposons que vous essayez de trouver 4 chiffres. Vous commencez avec [0,1,2,3], puis augmenter le dernier numéro à chaque fois (obtenir [0,1,2,4], [0,1,2,5] ...) jusqu'à ce que vous atteignez la limite [0,1,2,31]. Ensuite, augmenter le nombre avant-dernier et le dernier chiffre à un supérieur: [0,1,3,4]. Retour à l'augmentation du dernier numéro: [0,1,3,5], [0,1,3,6] ... etc Une fois que vous atteignez la fin de cela, vous allez revenir à [0,1,4 , 5] - finira par vous atteindre [0,1,30,31] à quel point vous devez revenir en arrière un peu plus loin: [0,2,3,4] et vous voilà parti à nouveau. Continuez jusqu'à ce que vous vous retrouvez finalement avec [28,29,30,31].

Étant donné un ensemble de nombres, il est évidemment facile de les convertir dans les 32 numéros de bits.

Answer 3

Vous voulez générer des combinaisons, voir cette Wikipedia article .

Answer 4

Vous avez besoin soit Factoradic (Google Permutations sur ce) ou l'un des algorithmes sur Wiki