Der folgende Link ist ein bisschen Hack, der zeigt, wie man den Modulus parallel zu 2 ^ n - 1 berechnet: ModulDivisionParallel
Können Sie erklären, wie diese Bitmanipulation funktioniert und wie die angegebene Schleife bei einem bestimmten Nenner aufgelöst wird (siehe Beispiel unten, woher kommen die Bitmasken)?
Beispiel für das Abrollen der Schleife für 0xF:
%Vor%Zunächst eine Klarstellung:
Wenn s = 4 (das heißt, der Modulus ist gleich 0xF ) bekomme ich folgendes entrolling:
Das ist sehr anders als das, was Sie in Ihrer Frage haben. Um zu erklären, warum das funktioniert:
Haben Sie schon einmal von Mathetricks gehört, wenn Sie alle Ziffern einer Zahl addieren und sie durch 9 teilbar ist, dann ist die ursprüngliche Zahl auch? Das funktioniert, weil der Rest, der das Original und die Summe um 9 teilt, gleich ist. Genau das machen wir hier, nur in einer anderen Basis - in Ihrem Beispiel mit hexadezimaler Basis.
Das Mathe-Kung-Fu ist das:
Der Beitrag jeder hexadezimalen Zahl zum endgültigen Wert kann als V * 16 ^ P dargestellt werden. Beachten Sie, dass 16 ^ P = 1 (mod 15) , also der Beitrag jedes Hexadezimalziffers zum endgültigen Wert einfach V (mod 15) ist. Mit anderen Worten, um den Gesamtbeitrag aller Ziffern zu erhalten, addieren Sie sie alle bis (mod 15) .
Die bitweisen Operationen sind nur eine clevere Methode, dies in logarithmischer Anzahl von Schritten zu tun: Fügen Sie der zweiten Hälfte wiederholt die erste Hälfte der hexadezimalen Ziffern hinzu.
Das Problem mit dem Neuner-Trick ist, dass Sie vielleicht eine zweistellige Zahl haben: 99 = 9 + 9 = 18 (mod 10)! Dann tust du es nochmal: 18 = 1 + 8 = 9 (mod 10).
Ebenso folgen wir den 'zusätzlichen' Iterationen von m = ((n >> 4) + (n & 0x0000000F) , bis die verbleibende Zahl eine Ziffer ist.
Jetzt ist das einzige verbleibende Detail, wenn wir 0xF als Ergebnis bekommen, in diesem Fall wollen wir stattdessen 0x0 .
Tags und Links algorithm language-agnostic c bit-manipulation