Ich bin gerade dabei, einen Baum-Enumerator zu schreiben, bei dem ich auf folgendes Problem gestoßen bin:
Ich betrachte maskierte Bitsets, dh Bitsets, bei denen die gesetzten Bits eine Teilmenge einer Maske sind, dh 0000101
mit Maske 1010101
. Was ich erreichen möchte, ist das Inkrementieren des Bitsets, jedoch nur in Bezug auf die maskierten Bits. In diesem Beispiel wäre das Ergebnis 0010000
. Um es etwas klarer zu machen, extrahieren Sie nur die maskierten Bits, dh 0011
erhöhen Sie sie auf 0100
und verteilen Sie sie erneut auf die Maskenbits 0010000
.
Sieht jemand einen effizienten Weg, dies zu tun, ohne die Operation von Hand mit einer Kombination aus Bitscans und Präfixmasken zu implementieren?
quelle
x
. Möglicherweisex = (x & ~mask) | (((x | ~mask) + 1) & mask);
.0101101
(zB.1.1.0.
in den Nicht-Masken-Bits und0.0.1.1
im "Zähler"), würden sie benötigen0111000
(einen neuen "Zähler"0.1.0.0
während der Aufbewahrung.1.1.0.
) oder ist einfach0010000
akzeptabel. Diese Antwort (und wahrscheinlich andere, obwohl ich nicht überprüft habe) geben letztere; Meine Version sollte die erstere geben, wenn dies erforderlich ist.Dies ist zwar im Vergleich zur akzeptierten Antwort nicht intuitiv, funktioniert jedoch in nur drei Schritten:
x = -(x ^ mask) & mask;
Dies kann wie von zch vorgeschlagen überprüft werden:
-(x ^ mask) = ~(x ^ mask) + 1 // assuming 2's complement = (x ^ ~mask) + 1 = (x | ~mask) + 1 // since x and ~mask have disjoint set bits
Dann entspricht es der akzeptierten Antwort.
quelle
-(x ^ mask) == (x | ~mask) + 1
wann immer x eine Teilmenge der Maske ist, und dann auf meine Antwort verweisen würden.-(x^mask) == ~((x ^ mask) - 1) == ~(x ^ mask) + 1 == (x ^ ~mask) + 1 == (x | ~mask) + 1
. Die letzte Gleichung gilt, weil Bitsätze disjunkt sind, andere sind immer wahr (zumindest in 2-Komplement).Wenn die Reihenfolge der Iteration nicht so wichtig ist und eine Dekrementierungsoperation Ihren Anforderungen entspricht, können nur zwei Operationen verwendet werden:
Lass uns beginnen mit
x = mask
und vorherigen Wert mit erhalten
x = (x - 1) & mask
x - 1
part ändert das letzte Nicht-Null-Bit auf Null und setzt alle weniger signifikanten Bits auf 1. Dann lässt der& mask
Teil nur Maskenbits zwischen ihnen.quelle