Beim Betrachten der x86-Assembly, die von einem Compiler erzeugt wurde, habe ich bemerkt, dass (nicht vorzeichenbehaftete) Integer-Divisionen manchmal als ganzzahlige Multiplikationen implementiert sind. Diese Optimierungen scheinen der Form
zu folgen %Vor%Zum Beispiel eine Division durch 9 durchführen:
%Vor% Eine Division durch 3 würde Multiplikation mit 0x55555555 + 1 usw. verwenden.
Ausnutzen der Tatsache, dass der Befehl mul den höchsten Teil des Ergebnisses im Register edx speichert, kann das Endergebnis der Division mit einer einzigen Multiplikation mit einem magischen Wert erhalten werden. (Obwohl diese Optimierung manchmal in Verbindung mit einer bitweisen Verschiebung am Ende verwendet wird.)
Ich hätte gerne einen Einblick, wie das eigentlich funktioniert. Wann ist dieser Ansatz gültig? Warum muss 1 zu unserer "magischen Zahl" hinzugefügt werden?
Diese Methode heißt "Division durch Invariante Multiplikation".
Die Konstanten, die Sie sehen, sind tatsächlich Näherungen des Reziproken.
Also eher als Computing:
%Vor%Sie tun stattdessen so etwas:
%Vor% wobei 1/D ein Kehrwert ist, der vorberechnet werden kann.
Grundsätzlich sind Kehrwerte ungenau, es sei denn D ist eine Zweierpotenz. Es wird also einen Rundungsfehler geben. Das +1 , das Sie sehen, ist dort, um den Rundungsfehler zu korrigieren.
Das häufigste Beispiel ist die Division durch 3:
%Vor% Wo 0xaaaaaaab = 2^33 / 3 + 1 .
Dieser Ansatz wird auf andere Teiler verallgemeinert.
Tags und Links optimization assembly bit-manipulation division multiplication