Un método rápido para redondear un doble a un int de 32 bits explicado

Al leer el código fuente de Lua , noté que Lua usa una macro para redondear un double a un int 32 bits. Extraje la macro , y se ve así:

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

Aquí ENDIANLOC se define como endianness , 0 para little endian, 1 para big endian. Lua maneja cuidadosamente la endianidad. t representa el tipo entero, como int o unsigned int .

Hice una pequeña investigación y hay un formato de macro más simple que usa el mismo pensamiento:

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

O en un estilo C ++:

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

Este truco puede funcionar en cualquier máquina que use IEEE 754 (lo que significa prácticamente todas las máquinas actuales). Funciona para números positivos y negativos, y el redondeo sigue la Regla del Banquero . (Esto no es sorprendente, ya que sigue a IEEE 754.)

Escribí un pequeño progtwig para probarlo:

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

Y produce -12345679, como se esperaba.

Me gustaría entrar en detalles sobre cómo funciona esta complicada macro . El número mágico 6755399441055744.0 es en realidad 2^51 + 2^52 , o 1.5 * 2^52 , y 1.5 en binario se puede representar como 1.1 . Cuando se agrega un número entero de 32 bits a este número mágico, bueno, estoy perdido desde aquí. ¿Cómo funciona este truco?

PD: Esto está en el código fuente de Lua, Llimits.h .

ACTUALIZAR :

  1. Como señala @Mysticial, este método no se limita a una int 32 bits, sino que también se puede expandir a int 64 bits, siempre que el número esté en el rango de 2 ^ 52. (La macro necesita algunas modificaciones)
  2. Algunos materiales dicen que este método no se puede usar en Direct3D .
  3. Cuando se trabaja con el ensamblador de Microsoft para x86, hay una macro escrita aún más rápida en el assembly (esta también se extrae de la fuente de Lua):

     #define double2int(i,n) __asm {__asm fld n __asm fistp i} 
  4. Hay un número mágico similar para el número de precisión simple: 1.5 * 2 ^23

Un double se representa así:

doble representación

y puede verse como dos enteros de 32 bits; ahora, el int tomado en todas las versiones de tu código (suponiendo que es un int 32 bits) es el de la derecha en la figura, entonces lo que estás haciendo al final es simplemente tomar los 32 bits más bajos de mantisa.


Ahora, al número mágico; como correctamente dijo, 6755399441055744 es 2 ^ 51 + 2 ^ 52; agregar ese número obliga al double a entrar en el “rango dulce” entre 2 ^ 52 y 2 ^ 53, lo que, como explica la Wikipedia aquí , tiene una propiedad interesante:

Entre 2 52 = 4,503,599,627,370,496 y 2 53 = 9,007,199,254,740,992 los números representables son exactamente los enteros

Esto se debe al hecho de que la mantisa tiene 52 bits de ancho.

El otro hecho interesante sobre la adición de 2 51 +2 52 es que afecta a la mantisa solo en los dos bits más altos, que se descartan de todos modos, ya que solo estamos tomando los 32 bits más bajos.


Por último, pero no menos importante: el signo.

El punto flotante IEEE 754 usa una representación de signo y magnitud, mientras que los enteros en máquinas “normales” usan la aritmética de complemento 2; ¿Cómo se maneja esto aquí?

Hablamos solo de enteros positivos; ahora supongamos que estamos tratando con un número negativo en el rango representable por un int 32 bits, entonces menos (en valor absoluto) que (-2 ^ 31 + 1); llámalo -a . Tal número obviamente se vuelve positivo al agregar el número mágico, y el valor resultante es 2 52 +2 51 + (- a).

Ahora, ¿qué obtenemos si interpretamos la mantisa en la representación del complemento a 2? Debe ser el resultado de la sum del complemento de 2 de (2 52 +2 51 ) y (-a). De nuevo, el primer término afecta solo a los dos bits superiores, lo que queda en los bits 0 ~ 50 es la representación complementaria de 2 (-a) (nuevamente, menos los dos bits superiores).

Dado que la reducción de un número de complemento de 2 a un ancho menor se realiza simplemente cortando los bits adicionales de la izquierda, tomar los 32 bits inferiores nos da correctamente (-a) en 32 bits, aritmética de complemento de 2.