Comptage, modèle de bits inversé

https://stackoverflow.com/questions/259212

06-07-2019
|

Question

J'essaie de trouver un algorithme pour compter de 0 à 2 ⁿ -1 mais leur structure binaire a été inversée. Je me soucie de seulement n LSB d'un mot. Comme vous l'avez peut-être deviné, j'ai échoué.

Pour n = 3:

000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

Vous avez l'idée.

Les réponses en pseudo-code sont excellentes. Les fragments de code dans toutes les langues sont les bienvenus, les réponses sans opérations sur les bits sont préférées.

Ne postez pas simplement un fragment sans même une courte explication ou un pointeur sur une source.

Modifier: j’ai oublié d’ajouter, j’ai déjà une implémentation naïve qui renverse un peu une variable de nombre. En un sens, cette méthode ne compte pas vraiment.

La solution

C’est, je pense plus facile avec les opérations sur les bits, même si vous avez dit que cela n’était pas préféré

En supposant que les inits 32 bits, voici un morceau de code astucieux qui peut inverser tous des bits sans le faire en 32 étapes:

 unsigned int i;
 i = (i & 0x55555555) <<  1 | (i & 0xaaaaaaaa) >>  1;
 i = (i & 0x33333333) <<  2 | (i & 0xcccccccc) >>  2;
 i = (i & 0x0f0f0f0f) <<  4 | (i & 0xf0f0f0f0) >>  4;
 i = (i & 0x00ff00ff) <<  8 | (i & 0xff00ff00) >>  8;
 i = (i & 0x0000ffff) << 16 | (i & 0xffff0000) >> 16;
 i >>= (32 - n);

Essentiellement, il s’agit d’un brassage entrelacé de tous les bits. Chaque fois, environ la moitié des bits de la valeur sont échangés avec l'autre moitié.

La dernière ligne est nécessaire pour réaligner les bits afin que bin " n " est le bit le plus significatif.

Des versions plus courtes de cela sont possibles si " n " est < = 16 ou < = 8

Autres conseils

À chaque étape, trouvez le chiffre 0 le plus à gauche de votre valeur. Réglez-le et effacez tous les chiffres à gauche de celui-ci. Si vous ne trouvez pas un chiffre 0, vous avez débordé: renvoyez 0, ou arrêtez, ou plantez, ou ce que vous voulez.

C’est ce qui se passe avec une incrémentation binaire normale (par ce que je veux dire par effet, pas comment elle est mise en œuvre dans le matériel), mais nous le faisons à gauche plutôt que à droite.

Que vous le fassiez en bits, en chaînes ou autre chose, à vous de choisir. Si vous le faites en bitops, alors un clz (ou un appel à une fonction équivalente de style hibit) sur ~value pourrait être le moyen le plus efficace: __builtin_clz, le cas échéant. Mais c’est un détail de mise en œuvre.

Cette solution était à l'origine en binaire et convertie en mathématique conventionnelle, comme spécifié par le demandeur.

Cela aurait plus de sens comme binaire, au moins la multiplication par 2 et la division par 2 devraient être < < 1 et & Gt; & Gt; 1 pour la rapidité, les additions et les soustractions n’ont probablement aucune importance.

Si vous passez masque au lieu de nBits, et que vous utilisez bitshifting au lieu de multiplier ou diviser, et que vous modifiez la récursion finale en boucle, ce sera probablement la solution la plus performante que vous trouverez, car rien ne le fera mais un seul ajout, il ne serait que lent que la solution d’Alnitak tous les 4, voire 8 appels.

int incrementBizarre(int initial, int nBits)
    // in the 3 bit example, this should create 100
    mask=2^(nBits-1)
    // This should only return true if the first (least significant) bit is not set
    // if initial is 011 and mask is 100
    //                3               4, bit is not set
    if(initial < mask)
        // If it was not, just set it and bail.
        return initial+ mask // 011 (3) + 100 (4) = 111 (7)
    else
        // it was set, are we at the most significant bit yet?
        // mask 100 (4) / 2 = 010 (2), 001/2 = 0 indicating overflow
        if(mask / 2) > 0
            // No, we were't, so unset it (initial-mask) and increment the next bit
            return incrementBizarre(initial - mask, mask/2)
        else
            // Whoops we were at the most significant bit.  Error condition
            throw new OverflowedMyBitsException()

Wow, ça s'est avéré plutôt cool. Je n'ai pas figuré dans la récursion jusqu'à la dernière seconde.

On se sent mal - comme si certaines opérations ne devraient pas fonctionner, mais elles le sont à cause de la nature de ce que vous faites (comme si vous pensiez que vous devriez avoir des problèmes lorsque vous travaillez à gauche sont non nulles, mais il s'avère que vous ne pouvez jamais opérer sur un bit à moins que tous les bits à gauche ne soient à zéro, ce qui est une condition très étrange, mais vraie.

Exemple de flux allant de 110 à 001 (en arrière de 3 à en arrière 4):

mask 100 (4), initial 110 (6); initial < mask=false; initial-mask = 010 (2), now try on the next bit
mask 010 (2), initial 010 (2); initial < mask=false; initial-mask = 000 (0), now inc the next bit
mask 001 (1), initial 000 (0); initial < mask=true;  initial + mask = 001--correct answer

Voici une solution de mon réponse à une autre question qui calcule le prochain index à inversion de bits sans effectuer de boucle. Il repose cependant beaucoup sur les opérations de bits.

L’idée principale est que l’incrémentation d’un nombre inverse simplement une séquence de bits les moins significatifs, par exemple de nnnn0111 à nnnn1000. Donc, afin de calculer le prochain index inversé, vous devez retourner une séquence de bits les plus significatifs. Si votre plate-forme cible a une instruction CTZ (& "; Compter les zéros finaux &"), Vous pouvez le faire efficacement.

Exemple en C utilisant GCC's __builtin_ctz:

void iter_reversed(unsigned bits) {
    unsigned n = 1 << bits;

    for (unsigned i = 0, j = 0; i < n; i++) {
        printf("%x\n", j);

        // Compute a mask of LSBs.
        unsigned mask = i ^ (i + 1);
        // Length of the mask.
        unsigned len = __builtin_ctz(~mask);
        // Align the mask to MSB of n.
        mask <<= bits - len;
        // XOR with mask.
        j ^= mask;
    }
}

Sans instruction CTZ, vous pouvez également utiliser la division entière:

void iter_reversed(unsigned bits) {
    unsigned n = 1 << bits;

    for (unsigned i = 0, j = 0; i < n; i++) {
        printf("%x\n", j);

        // Find least significant zero bit.
        unsigned bit = ~i & (i + 1);
        // Using division to bit-reverse a single bit.
        unsigned rev = (n / 2) / bit;
        // XOR with mask.
        j ^= (n - 1) & ~(rev - 1);
    }
}

void reverse(int nMaxVal, int nBits)
{
   int thisVal, bit, out;

   // Calculate for each value from 0 to nMaxVal.
   for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
   {
      out = 0;

      // Shift each bit from thisVal into out, in reverse order.
      for (bit=0; bit<nBits; ++bit)
         out = (out<<1) + ((thisVal>>bit) & 1)

   }
   printf("%d -> %d\n", thisVal, out);
}

Peut-être incrémentez-vous de 0 à N (& "; habituel &"; moyen & ";) et effectuez ReverseBitOrder () pour chaque itération. Vous pouvez trouver plusieurs implémentations ici (j'aime la LUT celle la meilleur). Devrait être très rapide.

Voici une réponse en Perl. Vous ne dites pas ce qui vient après le motif «tous les un», alors je retourne simplement zéro. J'ai sorti les opérations au niveau des bits afin qu'il soit facile de traduire dans une autre langue.

sub reverse_increment {
  my($n, $bits) = @_;

  my $carry = 2**$bits;
  while($carry > 1) {
    $carry /= 2;
    if($carry > $n) {
      return $carry + $n;
    } else {
      $n -= $carry;
    }
  }
  return 0;
}

Voici une solution qui n'essaye pas en réalité de faire des ajouts, mais exploite le modèle marche / arrêt de la séquence (la plupart des bits de sig alternent à chaque fois, le plus grand bit de sig alternant à chaque fois, etc.), ajustez n désiré:

#define FLIP(x, i) do { (x) ^= (1 << (i)); } while(0)

int main() {
    int n   = 3;
    int max = (1 << n);
    int x   = 0;

    for(int i = 1; i <= max; ++i) {
        std::cout << x << std::endl;
        /* if n == 3, this next part is functionally equivalent to this:
         *
         * if((i % 1) == 0) FLIP(x, n - 1);
         * if((i % 2) == 0) FLIP(x, n - 2);
         * if((i % 4) == 0) FLIP(x, n - 3);
         */
        for(int j = 0; j < n; ++j) {
            if((i % (1 << j)) == 0) FLIP(x, n - (j + 1));
        }                       
    }
}

Pourquoi ne pas ajouter 1 au bit de poids fort, puis passer au bit suivant (moins significatif), si nécessaire. Vous pouvez accélérer cela en utilisant des octets:

Précalculez une table de consultation pour le comptage en bits inversés de 0 à 256 (00000000 - > 10000000, 10000000 - > 01000000, ..., 11111111 - > 00000000).
Définissez tous les octets de votre numéro multi-octets sur zéro.
Incrémentez l'octet le plus significatif à l'aide de la table de recherche. Si l'octet est à 0, incrémentez l'octet suivant à l'aide de la table de recherche. Si l'octet est à 0, incrémenter l'octet suivant ...
Passez à l'étape 3.

Avec n comme puissance 2 et x la variable que vous souhaitez modifier:

(defun inv-step (x n)       ; the following is a function declaration
  "returns a bit-inverse step of x, bounded by 2^n"    ; documentation
  (do ((i (expt 2 (- n 1))  ; loop, init of i
          (/ i 2))          ; stepping of i
       (s x))               ; init of s as x
      ((not (integerp i))   ; breaking condition
       s)                   ; returned value if all bits are 1 (is 0 then)
    (if (< s i)                         ; the loop's body: if s < i
        (return-from inv-step (+ s i))  ;     -> add i to s and return the result
        (decf s i))))                   ;     else: reduce s by i

Je l'ai commenté à fond car vous ne connaissez peut-être pas cette syntaxe.

edit : voici la version récursive de queue. Cela semble être un peu plus rapide, à condition que vous ayez un compilateur avec optimisation des appels en aval.

(defun inv-step (x n)
  (let ((i (expt 2 (- n 1))))
    (cond ((= n 1)
           (if (zerop x) 1 0))         ; this is really (logxor x 1)                                                 
          ((< x i)
           (+ x i))
          (t
           (inv-step (- x i) (- n 1))))))

Lorsque vous inversez 0 to 2^n-1 mais que leur modèle de bits est inversé, vous couvrez presque toute la 0-2^n-1 séquence

Sum = 2^n * (2^n+1)/2

O(1) opération. Pas besoin de faire des inversions de bits

Modifier: Bien sûr, la question de l’affiche originale était sur le point d’être incrémentée d’une (inversée), ce qui rend les choses plus simples que d’ajouter deux valeurs aléatoires. La answer de nwellnhof contient déjà l'algorithme.

Somme des deux valeurs d'inversion de bits

Voici une solution en php:

function RevSum ($a,$b) {

    // loop until our adder, $b, is zero
    while ($b) {

        // get carry (aka overflow) bit for every bit-location by AND-operation
        // 0 + 0 --> 00   no overflow, carry is "0"
        // 0 + 1 --> 01   no overflow, carry is "0"
        // 1 + 0 --> 01   no overflow, carry is "0"
        // 1 + 1 --> 10   overflow! carry is "1"

        $c = $a & $b;


        // do 1-bit addition for every bit location at once by XOR-operation
        // 0 + 0 --> 00   result = 0
        // 0 + 1 --> 01   result = 1
        // 1 + 0 --> 01   result = 1
        // 1 + 1 --> 10   result = 0 (ignored that "1", already taken care above)

        $a ^= $b;


        // now: shift carry bits to the next bit-locations to be added to $a in
        // next iteration.
        // PHP_INT_MAX here is used to ensure that the most-significant bit of the
        // $b will be cleared after shifting. see link in the side note below.

        $b = ($c >> 1) & PHP_INT_MAX;

    }

    return $a;
}

Remarque secondaire: consultez cette question sur le décalage des valeurs négatives.

Et comme pour le test; commencer à partir de zéro et incrémenter la valeur de 8 bits inversés (10000000):

$value = 0;
$add = 0x80;    // 10000000 <-- "one" as bit reversed

for ($count = 20; $count--;) {      // loop 20 times
    printf("%08b\n", $value);       // show value as 8-bit binary
    $value = RevSum($value, $add);  // do addition
}

... produira:

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow