Zuerst wird eine Klarstellung:
Wenn s = 4 (das heißt, der Modul gleich 0xF) ich folgendes Abrollen erhalten:
m = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
m = ((n >> 16) + (n & 0x0000FFFF)
m = ((n >> 8) + (n & 0x000000FF)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = m == 0xF ? 0 : m;
Dies ist sehr anders als das, was Sie in Ihrer Frage haben. Um zu erklären, warum das funktioniert:
Haben Sie jemals von dem Mathetrick 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.
Die Mathematik kung-fu, ist dies:
Der Beitrag jeder hexadezimale Ziffer auf den Endwert kann als V * 16^P dargestellt werden. Beachten Sie, dass 16^P = 1 (mod 15), so jeder Beitrag der Hexadezimalziffer zum endgültigen Wert ist einfach V (mod 15). Mit anderen Worten, um den Gesamtbeitrag von allen Ziffern zu erhalten, fügen Sie sie alle (mod 15) hinzu.
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 9er-Trick ist, dass Sie mit einer zweistelligen Nummer enden können: 99 = 9 + 9 = 18 (mod 10)! Dann tust du es nochmal: 18 = 1 + 8 = 9 (mod 10).
In ähnlicher Weise folgen wir mit "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 das Ergebnis bekommen, in diesem Fall wollen wir 0x0 stattdessen.
Ja, das wusste ich. Ich arbeite an der Optimierung einer Assembly-Modul-Methode, die im Moment Verzweigungen und eine Maske der Form 2^n-1 verwendet. Also versuche ich die Äste loszuwerden und benutze stattdessen diese Methode. –
Interessant. Kann ich fragen, welche Art von Anwendung Sie verwenden, die ein Modul von 2^n-1 verwendet? Gibt es einen Grund, nicht stattdessen 2^n oder eine Primzahl zu verwenden? – JS1
@ JS1 Es ist nicht so ungewöhnlich. Ein Beispiel von vielen: Ein byteweiser Reed-Solomon-Code (Datenfehlererkennung und -korrektur) und Galois-Feld-basierte Algorithmen im Allgemeinen. Die Kodierung (von RS) ist einfach Code-mäßig, besteht hauptsächlich aus Schleifen, Additionen und Modulo (vorausgesetzt, dass einige statische Daten im Voraus berechnet werden, anstatt jedes Mal während der Dekodierung) – deviantfan