Eine schnelle Methode zum Runden eines Double auf ein 32-Bit-Int erklärt

Beim Lesen von Luas Quellcode habe ich festgestellt, dass Lua a verwendet macro, um a doubleauf 32 Bit zu runden int. Ich habe das extrahiert macround es sieht so aus:

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 ENDIANLOCwird Endianness definiert , 0für Little Endian, 1für Big Endian. Lua geht vorsichtig mit Endianness um. tsteht für den Integer-Typ, wie intoder unsigned int.

Ich habe ein wenig recherchiert und es gibt ein einfacheres Format macro, das denselben Gedanken 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 jeder Maschine mit IEEE 754 funktionieren (was heutzutage so ziemlich jede Maschine bedeutet). Es funktioniert sowohl für positive als auch für negative Zahlen, und die Rundung folgt der Banker-Regel . (Dies 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 erwartungsgemäß -12345679 aus.

Ich möchte ins Detail gehen, wie dies schwierig macrofunktioniert. Die magische Zahl 6755399441055744.0ist tatsächlich 2^51 + 2^52oder 1.5 * 2^52und und 1.5kann binär dargestellt werden als 1.1. Wenn eine 32-Bit-Ganzzahl zu dieser magischen Zahl hinzugefügt wird, bin ich von hier aus verloren. Wie funktioniert dieser Trick?

PS: Dies ist im Lua-Quellcode Llimits.h .

UPDATE :

1. Wie @Mysticial hervorhebt, beschränkt sich diese Methode nicht auf 32-Bit int, sondern kann auch auf 64-Bit erweitert werden, intsolange die Zahl im Bereich von 2 ^ 52 liegt. (Das macromuss geändert werden.)
2. Einige Materialien sagen, dass diese Methode in Direct3D nicht verwendet werden kann .

3. Wenn Sie mit Microsoft Assembler für x86 arbeiten, wird noch schneller macrogeschrieben assembly(dies wird 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

A doublewird folgendermaßen dargestellt:

und es kann als zwei 32-Bit-Ganzzahlen gesehen werden; Jetzt ist die intin allen Versionen Ihres Codes aufgenommene (vorausgesetzt, es handelt sich um eine 32-Bit-Version int) die rechts in der Abbildung. Am Ende nehmen Sie also nur die niedrigsten 32 Bit der Mantisse.

Nun zur magischen Zahl; Wie Sie richtig angegeben haben, ist 6755399441055744 2 ^ 51 + 2 ^ 52; Das Hinzufügen einer solchen Zahl zwingt die doubledazu, in den "süßen Bereich" zwischen 2 ^ 52 und 2 ^ 53 zu gehen, der, wie von Wikipedia hier erklärt , eine interessante Eigenschaft hat:

Zwischen 2 ⁵² = 4,503,599,627,370,496 und 2 ⁵³ = 9,007,199,254,740,992 sind die darstellbaren Zahlen genau die ganzen Zahlen

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

Die andere interessante Tatsache beim Hinzufügen von 2 ⁵¹ +2 ⁵² ist, dass es die Mantisse nur in den zwei höchsten Bits beeinflusst - die sowieso verworfen werden, da wir nur die niedrigsten 32 Bits nehmen.

Zu guter Letzt: das Schild.

IEEE 754-Gleitkomma verwendet eine Größen- und Vorzeichendarstellung, während Ganzzahlen auf "normalen" Maschinen die Komplementarithmetik von 2 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 ein 32-Bit dargestellt werden kann int, also weniger (im absoluten Wert) als (-2 ^ 31 + 1); nenn es -a. Eine solche Zahl wird offensichtlich durch Addition der magischen Zahl positiv gemacht, und der resultierende Wert ist 2 ⁵² +2 ⁵¹ + (- a).

Was bekommen wir nun, wenn wir die Mantisse in der Komplementdarstellung von 2 interpretieren? Es muss das Ergebnis der 2er-Komplementsumme von (2 ⁵² +2 ⁵¹ ) und (-a) sein. Wiederum wirkt sich der erste Term nur auf die oberen zwei Bits aus. Was in den Bits 0 bis 50 verbleibt, ist die Zweierkomplementdarstellung von (-a) (wiederum abzüglich der oberen zwei Bits).

Da die Reduzierung der Komplementzahl einer 2 auf eine kleinere Breite nur durch Wegschneiden der zusätzlichen Bits auf der linken Seite erfolgt, ergibt die korrekte (-a) 32-Komplement-Arithmetik von 2, wenn die unteren 32 Bits verwendet werden.