Mein Problem ist wie folgt: Ich habe einen Wert x und ein Muster p beide Variablen der gleichen Größe. Das Ziel besteht darin, alle Bitmuster von x zu durchlaufen, die nicht durch m maskiert sind.
Beispiel:
Wenn wir p = 1001 haben, möchten wir 0000 , 0001 , 1000 und 1001 finden - nicht unbedingt in dieser Reihenfolge.
Standardimplementierung in C99 (der Rückgabewert gibt an, ob wir bereits alle Werte zurückgegeben haben):
%Vor%Ich würde denken, dass es einen Trick geben sollte, um dies effizienter zu machen, aber ich kann keine großen Verbesserungen finden (abgesehen von der Berechnung der abschließenden Nullen der Maske und der richtigen Einstellung des Startwerts von inc, was nicht t viel von einer Verbesserung).
Edit: Wichtig ist auch die Tatsache, dass für jeden generierten Wert eine Menge zusätzlicher Arbeit generiert wird, was bedeutet, dass viele Duplikate nicht in Frage kommen (einige Duplikate, auch wenn sie nicht erkennbar sind, wären in Ordnung, es gibt keine Nebenwirkungen auf die Arbeit, es ist nur eine Verlangsamung).
Dies erzeugt alle Bitmuster in umgekehrter Reihenfolge (Anfangswert von val sollte gleich mask sein):
Und dieser (etwas weniger offensichtliche Code) erzeugt alle Bitmuster in direkter Reihenfolge (Anfangswert von val sollte Null sein):
Der optimalste Weg fühlt sich an:
Dies setzt natürlich voraus, dass das Mischen relativ effizient ist, andernfalls ist es einfacher, es zu bruten, indem man einfach von 0 bis zum größten möglichen Wert zählt, abhängig von der Gesamtzahl der Bits im Muster und Anwenden des Musters bei jeder Zählung. Das Erkennen von Duplikaten ist jedoch möglicherweise etwas teuer.
Für p = 9 (binary 1001 2 ) sind nur zwei Bits gesetzt, also wissen wir, dass es 2 2 = 4 zu erzeugende Werte gibt.
Wenn wir das Muster von rechts für 1-Bit scannen, können wir die folgende "Mischtabelle" bilden:
Also können wir von 0 bis 3 zählen und für jeden Wert entsprechend der Tabelle neu anordnen:
Tags und Links algorithm optimization c bit-manipulation