Incrémentation de jeux de bits "masqués

Question

Je suis actuellement en train d'écrire un énumérateur d'arbres et j'ai rencontré le problème suivant :

Je cherche des ensembles de bits masqués, c'est-à-dire des ensembles de bits où les bits de l'ensemble sont un sous-ensemble d'un masque. 0000101 avec masque 1010101 . Ce que je veux faire, c'est incrémenter le jeu de bits, mais uniquement en ce qui concerne les bits masqués. Dans cet exemple, le résultat serait 0010000 . Pour rendre les choses un peu plus claires, n'extrayez que les bits masqués, c.-à-d. 0011 et les incrémenter à 0100 et les distribuer à nouveau aux bits de masque, ce qui donne 0010000 .

Quelqu'un voit-il un moyen efficace de le faire, à moins d'implémenter l'opération à la main en utilisant une combinaison de balayages binaires et de masques de préfixe ?

Answer 1

Il suffit de remplir les bits non masqués avec des uns pour qu'ils propagent la retenue :

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;

Answer 2

Bien que cela ne soit pas intuitif par rapport à la réponse acceptée, cela fonctionne en seulement 3 étapes :

x = -(x ^ mask) & mask;

Ceci peut être vérifié comme suggéré par zch :

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

Elle devient alors équivalente à la réponse acceptée.

Answer 3

Si l'ordre d'itération n'est pas si important, et qu'une opération de décrémentation répond à vos besoins, il est possible de n'utiliser que deux opérations :

Commençons par

x = mask

et récupérer la valeur précédente avec

x = (x - 1) & mask

x - 1 change le dernier bit non nul en zéro, et met tous les bits moins significatifs à 1. Ensuite, & mask ne laisse que des bits de masque parmi eux.