Une méthode rapide pour arrondir un double en un int 32-bit a expliqué

Question

Lors de la lecture de Lua du code source, j'ai remarqué que Lua utilise un macro à la ronde un double 32 bits int. J'ai extrait l' macro, et il ressemble à ceci:

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

Ici, ENDIANLOC est définie comme l'endianness, 0 pour little endian, 1 pour big endian. Lua soigneusement poignées boutisme. t représente le type entier, comme int ou unsigned int.

J'ai fait une petite recherche et il y a un format plus simple d' macro qui utilise la même pensée:

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

Ou en C++-style:

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

Cette astuce peut travailler sur n'importe quel ordinateur à l'aide de la norme IEEE 754 (ce qui signifie à peu près toutes les machines d'aujourd'hui). Il fonctionne pour les nombres positifs et négatifs, et de l'arrondissement suit le Banquier est la Règle. (Ce n'est pas surprenant, car il suit la norme IEEE 754.)

J'ai écrit un petit programme pour tester:

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

Et c'sorties -12345679, comme prévu.

Je voudrais rentrer dans le détail comment cette délicate macro travaux. La magie nombre 6755399441055744.0 est en fait 2^51 + 2^52ou 1.5 * 2^52, et 1.5 en binaire peut être représenté comme 1.1. Lorsque l'un d'entier de 32 bits est ajouté à ce nombre magique, eh bien, je suis perdu à partir d'ici. Comment ce truc fonctionne?

P. S: C'est dans le code source en Lua, Llimits.h.

Mise à JOUR:

1. @Mysticial points, cette méthode ne se limite pas à un 32-bit int, il peut également être étendu à un nombre de 64 bits int , tant que le nombre est en la gamme de 2^52. ( macro Besoin de quelques modifications.)
2. Certains matériaux de dire que cette méthode ne peut pas être utilisé en Direct3D.

3. Lorsque vous travaillez avec Microsoft assembleur x86, il y a une même plus rapide macro écrit en assembly (ce qui est également extraites de Lua source):

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

4. Il y a une magie similaire numéro de simple précision nombre: 1.5 * 2 ^23

Answer 1

Un double est représenté comme ceci:

et il peut être considéré comme deux nombres entiers de 32 bits; maintenant, l' int prises dans toutes les versions de votre code (en supposant que c'est un 32 bits int) est le seul sur la droite dans la figure, de sorte que ce que vous faites dans la fin est juste de prendre la plus basse de 32 bits de la mantisse.

---

Maintenant, pour le nombre magique; comme vous l'avez si bien dit, 6755399441055744 est de 2^51 + 2^52; en ajoutant par exemple un certain nombre de forces de l' double à aller dans le "sweet gamme" entre les 2^52 et 2^53, qui, comme l'explique Wikipedia , ici, a une propriété intéressante:

Entre 2⁵²=4,503,599,627,370,496 et 2⁵³=9,007,199,254,740,992 le représentable chiffres sont exactement les entiers

Cela découle du fait que la mantisse est de 52 bits de large.

L'autre fait intéressant à propos de l'ajout de 2⁵¹+2⁵² est qu'il affecte la mantisse que dans les deux plus hautes bits qui sont éliminés de toute façon, puisque nous sommes en prendre seulement à son plus bas 32 bits.

---

Dernier mais non le moindre: le signe.

La norme IEEE 754 virgule flottante utilise une ampleur et le signe de la représentation, tandis que les entiers sur "normal" d'une machine 2 en complément à l'arithmétique; comment est-ce géré ici?

Nous avons parlé uniquement sur des entiers positifs; maintenant, supposons que nous avons affaire à un nombre négatif dans la gamme représentable par un 32-bit int, donc moins (en valeur absolue) que (-2^31+1); l'appellent -a. Un tel nombre est évidemment positif en ajoutant le nombre magique, et la valeur qui en résulte est de 2⁵²+2⁵¹+(-a).

Maintenant, que faisons-nous si nous interpréter la mantisse en complément de 2 représentation? Il doit être le résultat de 2 en complément à la somme de (2⁵²+2⁵¹) et (-a). Encore une fois, le premier terme n'affecte que la partie supérieure de deux bits, ce qui reste dans les bits 0~50 est le complément de 2 représentation de (- ) (encore une fois, moins la partie supérieure de deux bits).

Car la réduction d'un complément de 2 nombre à une plus petite largeur est fait simplement en coupant les extra bits sur la gauche, prendre la 32 bits de poids faible nous donne correctement (-a) en 32 bits, 2 en complément à l'arithmétique.