Eine schnelle Methode, um ein Double auf ein 32-Bit-Int zu runden, erklärt

Eine schnelle Methode, um ein Double auf ein 32-Bit-Int zu runden, erklärt


Beim Lesen von Luas Quellcode ist mir aufgefallen, dass Lua ein Makro verwendet, um double zu runden Werte auf 32-Bit int Werte. Das Makro wird im Llimits.h definiert Header-Datei und lautet wie folgt:


union i_cast {double d; int i[2]};
#define double2int(i, d, t) \
{volatile union i_cast u; u.d = (d) + 6755399441055744.0; \
(i) = (t)u.i[ENDIANLOC];}

Hier ENDIANLOC ist nach Endianness definiert:0 für Little-Endian, 1 für Big-Endian-Architekturen; Lua geht sorgfältig mit Endianness um. Die t argument wird durch einen ganzzahligen Typ wie int ersetzt oder unsigned int .


Ich habe ein wenig recherchiert und festgestellt, dass es ein einfacheres Format dieses Makros gibt, das dieselbe Technik verwendet:


#define double2int(i, d) \
{double t = ((d) + 6755399441055744.0); i = *((int *)(&t));}

Oder im C++-Stil:


inline int double2int(double d)
{
d += 6755399441055744.0;
return reinterpret_cast<int&>(d);
}

Dieser Trick kann auf jedem Computer mit IEEE 754 funktionieren (was heute so ziemlich auf jedem Computer bedeutet). Es funktioniert sowohl für positive als auch für negative Zahlen, und die Rundung folgt der Bankierregel. (Das ist nicht überraschend, da es IEEE 754 folgt.)


Ich habe ein kleines Programm geschrieben, um es zu testen:


int main()
{
double d = -12345678.9;
int i;
double2int(i, d)
printf("%d\n", i);
return 0;
}

Und es gibt -12345679 aus , wie erwartet.


Ich würde gerne verstehen, wie dieses knifflige Makro im Detail funktioniert. Die magische Zahl 6755399441055744.0 ist eigentlich 2 51 + 2 52 , oder 1,5 × 2 52 , und 1,5 im Binärformat kann als 1,1 dargestellt werden. Wenn eine beliebige 32-Bit-Ganzzahl zu dieser magischen Zahl hinzugefügt wird –


Nun, ich bin von hier aus verloren. Wie funktioniert dieser Trick?


Aktualisieren



  1. Wie @Mystcial betont, beschränkt sich diese Methode nicht auf einen 32-Bit-int , kann es auch auf ein 64-Bit int erweitert werden solange die Zahl im Bereich von 2 52 liegt . (Obwohl das Makro etwas modifiziert werden muss.)



  2. Einige Materialien besagen, dass diese Methode nicht in Direct3D verwendet werden kann.



  3. Wenn Sie mit Microsoft Assembler für x86 arbeiten, gibt es ein noch schnelleres Makro, das in Assembler-Code geschrieben ist (das Folgende ist auch aus der Lua-Quelle extrahiert):


     #define double2int(i,n)  __asm {__asm fld n   __asm fistp i}


  4. Es gibt eine ähnliche magische Zahl für Zahlen mit einfacher Genauigkeit:1,5 × 2 23 .




Antworten:


Ein Wert von double Der Gleitkommatyp wird wie folgt dargestellt:



und es kann als zwei 32-Bit-Ganzzahlen gesehen werden; jetzt die int alle Versionen Ihres Codes aufgenommen (vorausgesetzt, es handelt sich um eine 32-Bit-int ) ist das rechte in der Abbildung, also nehmen Sie am Ende nur die niedrigsten 32 Bits der Mantisse.



Nun zur magischen Zahl; Wie Sie richtig gesagt haben, ist 6755399441055744 2 51 + 2 52 ; Das Hinzufügen einer solchen Zahl erzwingt den double in den „süßen Bereich“ zwischen 2 52 zu gehen und 2 53 , die, wie von Wikipedia erklärt, eine interessante Eigenschaft hat:



Dies folgt aus der Tatsache, dass die Mantisse 52 Bit breit ist.


Die andere interessante Tatsache über das Addieren von 2 51 + 2 52 ist, dass es die Mantisse nur in den beiden höchsten Bits beeinflusst – die sowieso verworfen werden, da wir nur die niedrigsten 32 Bits nehmen.



Last but not least:das Schild.


IEEE 754-Gleitkomma verwendet eine Größen- und Vorzeichendarstellung, während ganze Zahlen auf "normalen" Maschinen die 2er-Komplement-Arithmetik verwenden; wie wird das hier gehandhabt?


Wir haben nur über positive ganze Zahlen gesprochen; Nehmen wir nun an, wir haben es mit einer negativen Zahl in dem Bereich zu tun, der durch einen 32-Bit-int darstellbar ist , also weniger (im absoluten Wert) als (−2 31 + 1); nenne es -a. Eine solche Zahl wird offensichtlich positiv gemacht, indem man die magische Zahl hinzufügt, und der resultierende Wert ist 2 52 + 2 51 + (-a).


Was bekommen wir nun, wenn wir die Mantisse in der 2er-Komplement-Darstellung interpretieren? Es muss das Ergebnis der 2er-Komplementsumme von (2 52 sein + 2 51 ) und (-a). Auch hier betrifft der erste Term nur die oberen zwei Bits, was in den Bits 0–50 verbleibt, ist die 2er-Komplementdarstellung von (-a) (wieder minus die oberen zwei Bits).


Da die Reduzierung einer 2er-Komplementzahl auf eine kleinere Breite einfach durch Wegschneiden der zusätzlichen Bits auf der linken Seite erfolgt, ergibt die Verwendung der unteren 32 Bits in 32-Bit-2er-Komplement-Arithmetik korrekt (−a).


Einige Code-Antworten


union i_cast {double d;
int i[2]};
#define double2int(i, d, t) \
{volatile union i_cast u;
u.d = (d) + 6755399441055744.0;
\
(i) = (t)u.i[ENDIANLOC];}
#define double2int(i, d) \
{double t = ((d) + 6755399441055744.0);
i = *((int *)(&t));}
inline int double2int(double d) {
d += 6755399441055744.0;
return reinterpret_cast<int&>(d);
}
int main() {
double d = -12345678.9;
int i;
double2int(i, d)
printf("%d\n", i);
return 0;
}
 #define double2int(i,n)  __asm {__asm fld n   __asm fistp i} 
  (2^52+2^51, or base2 of 110 then [50 zeros] 
  0x  0018 0000 0000 0000 (18e12) 
  0 300 00000 00000 00000 ( 3e17) 
/**  * Round to the nearest integer.  * for tie-breaks: round half to even (bankers' rounding)  * Only works for inputs in the range: [-2^51, 2^51]  */ inline double rint(double d) {
double x = 6755399441055744.0;
// 2^51 + 2^52
return d + x - x;
}
#include <cstdio>
int main() {
// round to nearest integer
printf("%.1f, %.1f\n", rint(-12345678.3), rint(-12345678.9));
// test tie-breaking rule
printf("%.1f, %.1f, %.1f, %.1f\n", rint(-24.5), rint(-23.5), rint(23.5), rint(24.5));
return 0;
} // output: // -12345678.0, -12345679.0 // -24.0, -24.0, 24.0, 24.0