c++ - Bitset "mascherati" in aumento




bit-manipulation intrinsics (2)

Attualmente sto scrivendo un enumeratore di alberi in cui ho riscontrato il seguente problema:

Sto osservando i bitset mascherati, ovvero i bitset in cui i bit impostati sono un sottoinsieme di una maschera, ovvero 0000101 con la maschera 1010101 . Quello che voglio realizzare è incrementare il bitset, ma solo rispetto ai bit mascherati. In questo esempio, il risultato sarebbe 0010000 . Per renderlo un po 'più chiaro, estrarre solo i bit mascherati, ovvero 0011 , incrementarli a 0100 e distribuirli nuovamente ai bit della maschera, dando 0010000 .

Qualcuno vede un modo efficace per farlo, a parte l'implementazione manuale dell'operazione usando una combinazione di bitcan e maschere prefisso?


Basta riempire i bit non maschera con quelli in modo che si propagino trasportano:

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

Se l'ordine di iterazione non è così importante e un'operazione di decremento soddisferà le tue esigenze, è possibile utilizzare solo due operazioni:

Iniziamo con

x = mask

e ottieni il valore precedente con

x = (x - 1) & mask

x - 1 parte cambia l'ultimo bit diverso da zero su zero e imposta tutti i bit meno significativi su 1. Quindi la parte & mask lascia solo frammenti di maschera tra di loro.





intrinsics