Ich habe eine interessante Technik gesehen, die bei der Beantwortung einer anderen Frage verwendet wurde , und möchte sie etwas besser verstehen.
Wir erhalten eine vorzeichenlose 64-Bit-Ganzzahl und interessieren uns für die folgenden Bits:
1.......2.......3.......4.......5.......6.......7.......8.......
Insbesondere möchten wir sie wie folgt auf die ersten acht Positionen verschieben:
12345678........................................................
Der Wert der durch angegebenen Bits ist uns egal .
und sie müssen nicht erhalten bleiben.
Die Lösung bestand darin, die unerwünschten Bits auszublenden und das Ergebnis mit zu multiplizieren 0x2040810204081
. Wie sich herausstellt, ist dies der Trick.
Wie allgemein ist diese Methode? Kann diese Technik verwendet werden, um eine Teilmenge von Bits zu extrahieren? Wenn nicht, wie kann man herausfinden, ob die Methode für einen bestimmten Satz von Bits funktioniert oder nicht?
Wie würde man schließlich den (a?) Richtigen Multiplikator finden, um die gegebenen Bits zu extrahieren?
Antworten:
Sehr interessante Frage und kluger Trick.
Schauen wir uns ein einfaches Beispiel für die Manipulation eines einzelnen Bytes an. Der Einfachheit halber wird vorzeichenloses 8-Bit verwendet. Stellen Sie sich vor, Ihre Nummer ist
xxaxxbxx
und Sie wollenab000000
.Die Lösung bestand aus zwei Schritten: einer Bitmaskierung, gefolgt von einer Multiplikation. Die Bitmaske ist eine einfache UND-Operation, die uninteressante Bits in Nullen umwandelt. Im obigen Fall wäre Ihre Maske
00100100
und das Ergebnis00a00b00
.Nun der schwierige Teil: das zu machen
ab......
.Eine Multiplikation ist eine Reihe von Shift-and-Add-Operationen. Der Schlüssel ist, dass der Überlauf die nicht benötigten Bits "wegschiebt" und die gewünschten an die richtige Stelle bringt.
Die Multiplikation mit 4 (
00000100
) würde alles, was übrig bleibt, um 2 verschieben und Sie dazu bringena00b0000
. Um dasb
nach oben zu bringen, müssen wir mit 1 multiplizieren (um das a an der richtigen Stelle zu halten) + 4 (um das b nach oben zu bewegen). Diese Summe ist 5 und zusammen mit den früheren 4 erhalten wir eine magische Zahl von 20 oder00010100
. Das Original war00a00b00
nach dem Maskieren; Die Multiplikation ergibt:Von diesem Ansatz aus können Sie auf größere Zahlen und mehr Bits erweitern.
Eine der Fragen, die Sie gestellt haben, war: "Kann dies mit einer beliebigen Anzahl von Bits durchgeführt werden?" Ich denke, die Antwort ist "nein", es sei denn, Sie erlauben mehrere Maskierungsoperationen oder mehrere Multiplikationen. Das Problem ist das Problem der "Kollisionen" - zum Beispiel das "Streuner b" im obigen Problem. Stellen Sie sich vor, wir müssen dies mit einer Zahl wie tun
xaxxbxxcx
. Nach dem früheren Ansatz würden Sie denken, wir brauchen {x 2, x {1 + 4 + 16}} = x 42 (oooh - die Antwort auf alles!). Ergebnis:Wie Sie sehen können, funktioniert es immer noch, aber "nur gerade". Der Schlüssel hier ist, dass zwischen den Bits, die wir wollen, "genug Platz" ist, damit wir alles zusammenpressen können. Ich konnte kein viertes Bit d direkt nach c hinzufügen, da ich Fälle bekommen würde, in denen ich c + d bekomme, Bits könnten tragen, ...
Ohne formalen Beweis würde ich die interessanteren Teile Ihrer Frage wie folgt beantworten: "Nein, dies funktioniert nicht für eine beliebige Anzahl von Bits. Um N Bits zu extrahieren, benötigen Sie (N-1) Leerzeichen zwischen den gewünschten Bits extrahieren oder zusätzliche Maskenmultiplikationsschritte ausführen. "
Die einzige Ausnahme, die ich mir für die Regel "Muss (N-1) Nullen zwischen Bits haben" vorstellen kann, ist folgende: Wenn Sie zwei Bits extrahieren möchten, die im Original nebeneinander liegen, UND Sie sie in der behalten möchten gleiche Reihenfolge, dann können Sie es noch tun. Und für die Zwecke der (N-1) -Regel zählen sie als zwei Bits.
Es gibt noch eine weitere Erkenntnis - inspiriert von der Antwort von @Ternary unten (siehe meinen Kommentar dort). Für jedes interessante Bit benötigen Sie nur so viele Nullen rechts davon, wie Sie Platz für Bits benötigen, die dorthin gehen müssen. Aber es braucht auch so viele Bits links wie es Ergebnisbits links hat. Wenn also ein Bit b an der Position m von n landet, muss es links m-1 Nullen und rechts nm Nullen haben. Insbesondere wenn die Bits in der ursprünglichen Nummer nicht in der gleichen Reihenfolge sind wie nach der Neuordnung, ist dies eine wichtige Verbesserung der ursprünglichen Kriterien. Dies bedeutet zum Beispiel, dass ein 16-Bit-Wort
Kann verschoben werden in
obwohl es nur einen Raum zwischen e und b gibt, zwei zwischen d und c, drei zwischen den anderen. Was ist mit N-1 passiert? In diesem Fall
a...e
wird "ein Block" - sie werden mit 1 multipliziert, um an der richtigen Stelle zu landen, und so "wir haben e kostenlos". Gleiches gilt für b und d (b benötigt drei Leerzeichen rechts, d benötigt die gleichen drei links). Wenn wir also die magische Zahl berechnen, stellen wir fest, dass es Duplikate gibt:Wenn Sie diese Nummern in einer anderen Reihenfolge haben möchten, müssen Sie sie natürlich weiter platzieren. Wir können die
(N-1)
Regel neu formulieren : "Es wird immer funktionieren, wenn mindestens (N-1) Leerzeichen zwischen den Bits vorhanden sind; oder wenn die Reihenfolge der Bits im Endergebnis bekannt ist, wenn ein Bit b in Position m von endet n, es muss links m-1 Nullen und rechts nm Nullen haben. "@Ternary wies darauf hin, dass diese Regel nicht ganz funktioniert, da es einen Übertrag von Bits geben kann, die "rechts neben dem Zielbereich" hinzufügen - nämlich wenn die Bits, nach denen wir suchen, alle diejenigen sind. Fortsetzung des obigen Beispiels mit den fünf dicht gepackten Bits in einem 16-Bit-Wort: Wenn wir mit beginnen
Der Einfachheit halber werde ich die Bitpositionen benennen
ABCDEFGHIJKLMNOP
Die Mathematik, die wir machen wollten, war
Bis jetzt dachten wir, dass alles unten
abcde
(PositionenABCDE
) keine Rolle spielen würde, aber tatsächlich, wie @Ternary hervorhob, wennb=1, c=1, d=1
dann(b+c)
in PositionG
ein bisschen in Position gebracht wirdF
, was bedeutet, dass(d+1)
in PositionF
ein bisschen inE
- und unsere Ergebnis ist verwöhnt. Beachten Sie, dass der Platz rechts neben dem niedrigstwertigen interessierenden Bit (c
in diesem Beispiel) keine Rolle spielt, da die Multiplikation ein Auffüllen mit Nullen von jenseits des niedrigstwertigen Bits verursacht.Wir müssen also unsere (m-1) / (nm) -Regel ändern. Wenn es mehr als ein Bit gibt, das "genau (nm) unbenutzte Bits rechts hat (ohne das letzte Bit im Muster zu zählen -" c "im obigen Beispiel), müssen wir die Regel verstärken - und wir müssen mach das iterativ!
Wir müssen nicht nur die Anzahl der Bits betrachten, die das (nm) -Kriterium erfüllen, sondern auch diejenigen, die bei (n-m + 1) usw. liegen. Nennen wir ihre Anzahl Q0 (genau
n-m
zum nächsten Bit), Q1 ( n-m + 1) bis zu Q (N-1) (n-1). Dann riskieren wir zu tragen, wennWenn Sie sich das ansehen, können Sie das sehen, wenn Sie einen einfachen mathematischen Ausdruck schreiben
und das Ergebnis ist
W > 2 * N
, dann müssen Sie das RHS-Kriterium um ein Bit auf erhöhen(n-m+1)
. Zu diesem Zeitpunkt ist der Betrieb sicher, solangeW < 4
; Wenn dies nicht funktioniert, erhöhen Sie das Kriterium noch einmal usw.Ich denke, dass das Befolgen der obigen Anweisungen einen langen Weg zu Ihrer Antwort bringt ...
quelle
Sehr interessante Frage. Ich stimme meinen zwei Cent zu, das heißt, wenn Sie es schaffen, Probleme wie diese in Bezug auf die Logik erster Ordnung über die Bitvektortheorie zu erklären, dann sind Theorembeweiser Ihr Freund und können Sie möglicherweise sehr schnell versorgen Antworten auf Ihre Fragen. Lassen Sie uns das gestellte Problem als Theorem wiederholen:
"Es gibt einige 64-Bit-Konstanten 'mask' und 'multiplicand', so dass wir für alle 64-Bit-Bitvektoren x im Ausdruck y = (x & mask) * multiplicand y.63 == x.63 haben , y.62 == x.55, y.61 == x.47 usw. "
Wenn dieser Satz tatsächlich ein Theorem ist, dann ist es wahr, dass einige Werte der Konstanten 'mask' und 'multiplicand' diese Eigenschaft erfüllen. Lassen Sie uns dies in Bezug auf etwas formulieren, das ein Theorembeweiser verstehen kann, nämlich die Eingabe von SMT-LIB 2:
Und jetzt fragen wir den Theorembeweiser Z3, ob dies ein Theorem ist:
Das Ergebnis ist:
Bingo! Es reproduziert das im ursprünglichen Beitrag angegebene Ergebnis in 0,06 Sekunden.
Wenn wir dies aus einer allgemeineren Perspektive betrachten, können wir dies als ein Beispiel für ein Programmsyntheseproblem erster Ordnung betrachten, das ein aufstrebendes Forschungsgebiet ist, über das nur wenige Artikel veröffentlicht wurden. Eine Suche nach
"program synthesis" filetype:pdf
sollte Ihnen den Einstieg erleichtern.quelle
Jedes 1-Bit im Multiplikator wird verwendet, um eines der Bits an die richtige Position zu kopieren:
1
ist bereits in der richtigen Position, also multiplizieren Sie mit0x0000000000000001
.2
muss um 7 Bitpositionen nach links verschoben werden, damit wir mit multiplizieren0x0000000000000080
(Bit 7 ist gesetzt).3
muss um 14 Bitpositionen nach links verschoben werden, damit wir mit multiplizieren0x0000000000000400
(Bit 14 ist gesetzt).8
muss um 49 Bitpositionen nach links verschoben werden, damit wir mit multiplizieren0x0002000000000000
(Bit 49 ist gesetzt).Der Multiplikator ist die Summe der Multiplikatoren für die einzelnen Bits.
Dies funktioniert nur, weil die zu sammelnden Bits nicht zu nahe beieinander liegen, so dass die Multiplikation von Bits, die in unserem Schema nicht zusammengehören, entweder über das 64-Bit oder im unteren, nicht interessierenden Teil hinausgeht.
Beachten Sie, dass die anderen Bits in der ursprünglichen Nummer sein müssen
0
. Dies kann erreicht werden, indem sie mit einer UND-Operation maskiert werden.quelle
(Ich hatte es noch nie gesehen. Dieser Trick ist großartig!)
Ich werde ein wenig auf Floris 'Behauptung eingehen, dass Sie beim Extrahieren von
n
Bitsn-1
Platz zwischen nicht aufeinanderfolgenden Bits benötigen :Mein erster Gedanke (wir werden gleich sehen, dass dies nicht ganz funktioniert) war, dass Sie es besser machen könnten: Wenn Sie
n
Bits extrahieren möchten , kommt es beim Extrahieren / Verschieben von Bits zu einer Kollision,i
wenn Sie jemanden haben (nicht -konsekutiv mit Biti
) in deri-1
vorhergehenden odern-i
nachfolgenden Bits.Ich werde einige Beispiele zur Veranschaulichung geben:
...a..b...c...
Funktioniert (niemand in den 2 Bits nacha
, das Bit vor und das Bit nachb
, und niemand ist in den 2 Bits vorc
):...a.b....c...
Schlägt fehl, weilb
es in den 2 Bits danach ista
(und beim Verschieben an die Stelle eines anderen gezogen wirda
):...a...b.c...
Schlägt fehl, weilb
es sich um die 2 vorhergehenden Bits handeltc
(und beim Verschieben an die Stelle eines anderen geschoben wirdc
):...a...bc...d...
Funktioniert, weil aufeinanderfolgende Bits zusammen verschoben werden:Aber wir haben ein Problem. Wenn wir
n-i
stattdessen verwendenn-1
, könnten wir das folgende Szenario haben: Was ist, wenn wir eine Kollision außerhalb des Teils haben, die uns wichtig ist, etwas, das wir am Ende maskieren würden, dessen Übertragsbits jedoch den wichtigen nicht maskierten Bereich stören ? (und Hinweis: Dien-1
Anforderung stellt sicher, dass dies nicht geschieht, indem sichergestellt wird, dass diei-1
Bits nach unserem nicht maskierten Bereich klar sind, wenn wir dasi
th-Bit verschieben.)...a...b..c...d...
Ein möglicher Fehler bei Übertragsbitsc
liegt imn-1
Nachhineinb
, erfüllt jedoch dien-i
Kriterien:Warum kehren wir nicht einfach zu dieser
n-1
Anforderung an " Platz" zurück? Weil wir es besser machen können :...a....b..c...d..
Dern-1
Test " Bits of Space" schlägt fehl , funktioniert jedoch für unseren Trick zum Extrahieren von Bits:Ich kann nicht mit einem guten Weg, um diese Felder zu charakterisieren , die nicht haben
n-1
, Raum zwischen wichtigen Bits , aber immer noch für unsere Operation funktionieren würde. Da wir es aber vorher wissen welchen Bits wir interessiert sind, können wir unseren Filter überprüfen, um sicherzustellen, dass keine Carry-Bit-Kollisionen auftreten:Vergleichen Sie
(-1 AND mask) * shift
mit dem erwarteten All-One-Ergebnis,-1 << (64-n)
(für 64-Bit ohne Vorzeichen).Die magische Verschiebung / Multiplikation zum Extrahieren unserer Bits funktioniert genau dann, wenn beide gleich sind.
quelle
b
an der Positionm
von landetn
, muss esm-1
linksn-m-1
Nullen und rechts Nullen haben. Insbesondere wenn die Bits in der ursprünglichen Nummer nicht in der gleichen Reihenfolge sind wie nach der Neuordnung, ist dies eine wichtige Verbesserung der ursprünglichen Kriterien. Das macht Spaß.Zusätzlich zu den bereits hervorragenden Antworten auf diese sehr interessante Frage könnte es nützlich sein zu wissen, dass dieser bitweise Multiplikationstrick in der Computerschach-Community seit 2007 bekannt ist und unter dem Namen Magic BitBoards firmiert .
Viele Computerschach-Engines verwenden mehrere 64-Bit-Ganzzahlen (sogenannte Bitboards), um die verschiedenen Stückmengen darzustellen (1 Bit pro belegtem Quadrat). Angenommen, ein Gleitstück (Turm, Bischof, Königin) auf einem bestimmten Ursprungsfeld kann sich auf höchstens
K
Felder bewegen, wenn keine blockierenden Teile vorhanden sind. Die Verwendung von bitweisen und dieser gestreutenK
Bits mit dem Bitboard der belegten Quadrate ergibt ein spezifischesK
Bit-Wort, das in eine 64-Bit-Ganzzahl eingebettet ist.Die magische Multiplikation kann verwendet werden, um diese gestreuten
K
Bits den unterenK
Bits einer 64-Bit-Ganzzahl zuzuordnen . Diese unterenK
Bits können dann verwendet werden, um eine Tabelle vorberechneter Bitboards zu indizieren, die die zulässigen Quadrate darstellen, zu denen sich das Teil auf seinem Ursprungsquadrat tatsächlich bewegen kann (wobei darauf geachtet wird, Teile zu blockieren usw.).Eine typische Schachmaschine, die diesen Ansatz verwendet, verfügt über 2 Tabellen (eine für Türme, eine für Bischöfe, Königinnen, die beide kombinieren) mit 64 Einträgen (eine pro Ursprungsquadrat), die solche vorberechneten Ergebnisse enthalten. Sowohl die Closed Source ( Houdini ) mit der höchsten Bewertung als auch die Open Source-Schachengine ( Stockfish ) verwenden diesen Ansatz derzeit für seine sehr hohe Leistung.
Das Finden dieser magischen Multiplikatoren erfolgt entweder mithilfe einer umfassenden Suche (optimiert mit frühen Cutoffs) oder mit Trial and Erorr (z. B. Ausprobieren zufälliger 64-Bit-Ganzzahlen). Während der Bewegungsgenerierung wurden keine Bitmuster verwendet, für die keine magische Konstante gefunden werden konnte. Bitweise Übertragseffekte sind jedoch typischerweise erforderlich, wenn die abzubildenden Bits (fast) benachbarte Indizes haben.
AFAIK, der sehr allgemeine SAT-Löser-Ansatz von @Syzygy, wurde im Computerschach nicht verwendet, und es scheint auch keine formale Theorie bezüglich der Existenz und Einzigartigkeit solcher magischen Konstanten zu geben.
quelle