Szybka metoda zaokrąglić podwójna do 32-bitowego int wyjaśnił

Question

Czytając Lua's kodu źródłowego, zauważyłem, że Lua wykorzystuje macro się wokół double do 32-bitowego int. I wyjął macro, a wygląda to tak:

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];} 

Tutaj ENDIANLOC jest zdefiniowany jako endianness, 0 dla little endian, 1 dla big endian. Lua ostrożnie obchodzi się z endianizmem. t oznacza typu Integer jak int lub unsigned int.

Zrobiłem trochę badań i istnieje prostszy format macro który wykorzystuje tę samą myśl:

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

Albo w C++ - stylu:

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

Ta sztuczka może pracować na dowolnym komputerze używając IEEE 754 (co oznacza prawie każdy komputer dzisiaj). Działa zarówno dla liczb dodatnich, jak i ujemnych, a zaokrąglanie następuje po Banker's Rule. (Nie jest to zaskakujące, ponieważ następuje IEEE   754.)

napisałem mały program, aby go przetestować:

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

I wyprowadza -12345679, jak oczekiwano.

Chciałbym dostać się do szczegółów, jak to skomplikowane macro prace. Magiczny numer 6755399441055744.0 jest rzeczywiście 2^51 + 2^52 lub 1.5 * 2^52 i 1.5 binarnie może być reprezentowana jako 1.1. Kiedy do tej magicznej liczby dodana jest jakakolwiek 32-bitowa liczba całkowita, cóż, jestem stąd zagubiony. Jak działa ta sztuczka?

P.S: To jest w kodzie źródłowym Lua, Llimits.h.

UPDATE:

1. W @Mysticial wskazuje to sposób nie ogranicza się do 32-bitowego int, może być rozszerzony do 64 bitów int dopóki numer jest w w zakresie 2^52. (The macro potrzebuje modyfikacji.)
2. Niektóre materiały powiedzieć, że sposób ten nie może być stosowany w Direct3D.

3. Podczas pracy z Microsoft asemblerze dla x86, nie ma nawet szybciej macro napisany w assembly (jest również uzyskiwany z źródła Lua):

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

4. Jest podobny magiczna liczba dla jednego numeru precyzji: 1.5 * 2 ^23

Answer 1

double jest reprezentowana następująco:

i może być widziana jako dwie 32-bitowe liczby całkowite; teraz, int wzięty we wszystkich wersjach twojego kodu (przypuśćmy, że jest to 32-bitowy int) jest tym po prawej stronie na rysunku, więc to, co robisz na końcu, to po prostu przyjmowanie najniższych 32 bitów mantysy.

---

Teraz, do magicznej liczby; jak poprawnie stwierdzono, 6755399441055744 to 2^51 + 2^52; dodając taką ilość Wymusza double wejść do "sweet zakresie" od 2^52 a 2^53, które, jak wyjaśniono w Wikipedia here, posiada interesujące właściwości:

pomiędzy 2 = 4,503,599,627,370,496 i 2 = 9.007.199.254.740.992 z zakodowania numery są dokładnie całkowite

wynika to z faktu, że mantysa wynosi 52 bitów szerokości.

Drugi interesujący jest okoliczność, dodając 2 +2 jest to, że ma to wpływ na mantysę tylko w dwóch najwyższych bitów - które są usuwane tak, ponieważ przyjmuje tylko jej najniższe 32 bitów.

---

Last but not least: the sign.

Punkt zmiennoprzecinkowy IEEE 754 używa reprezentacji wartości i znaku, natomiast liczby całkowite na "normalnych" maszynach wykorzystują arytmetyczną liczbę uzupełnień 2; jak to się tutaj dzieje?

Rozmawialiśmy tylko o liczbach całkowitych dodatnich; teraz załóżmy, że mamy do czynienia z liczbą ujemną w zakresie reprezentowanym przez 32-bitową int, więc mniej (w wartości bezwzględnej) niż (-2^31 + 1); nazwij to -a. Taka liczba jest oczywiście dodatnia dzięki dodaniu magicznej liczby, a wynikowa wartość to 2 +2 + (- a).

Teraz, co otrzymamy, jeśli interpretujemy mantysę w reprezentacji uzupełnienia 2? Musi to być wynik sumy uzupełniającej 2 (2 +2) i (-a). Ponownie, pierwszy termin wpływa tylko na górne dwa bity, to, co pozostaje w bitach 0 ~ 50, jest uzupełnieniem 2 do -a (ponownie, minus dwa górne bity).

Ponieważ redukcja liczby dopełnień o 2 do mniejszej szerokości jest wykonywana po prostu przez odcięcie dodatkowych bitów po lewej stronie, pobranie niższych 32 bitów daje nam poprawnie (-a) w arytmetyce uzupełnień 32-bitowych, 2-tych.