Быстрый метод для округления двойного до 32-битного int

При чтении исходного кода Lua's я заметил, что Lua использует macro для округления double до 32-разрядного int. Я извлек macro, и он выглядит так:

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

Здесь ENDIANLOC определяется как endianness, 0 для маленького endian, 1 для большого endian. Lua тщательно обрабатывает сущность. t обозначает целочисленный тип, например int или unsigned int.

Я провел небольшое исследование и там был более простой формат macro, который использует ту же мысль:

#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);
}

Этот трюк может работать на любой машине, используя IEEE 754 (что означает почти все машины сегодня). Он работает как для положительных, так и для отрицательных чисел, а округление следует за Правилом банкира. (Это не удивительно, так как это следует за IEEE 754.)

Я написал небольшую программу для тестирования:

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

И он выводит -12345679, как и ожидалось.

Я хотел бы подробно рассказать, как работает этот сложный macro. Магическое число 6755399441055744.0 на самом деле 2^51 + 2^52 или 1.5 * 2^52, а 1.5 в двоичном формате может быть представлено как 1.1. Когда к этому магическому числу добавляется любое 32-битное целое число, ну, я проиграл здесь. Как этот трюк работает?

P.S: Это в исходном коде Lua, Llimits.h.

UPDATE

  • Как отмечает @Mysticial, этот метод не ограничивается 32-разрядным int, он также может быть расширен до 64-битного int, пока номер находится в диапазон 2 ^ 52. (macro нуждается в некоторой модификации.)
  • Некоторые материалы говорят, что этот метод нельзя использовать в Direct3D.

  • При работе с ассемблером Microsoft для x86 существует четное быстрее macro, записанный в assembly (это также извлекается из источника Lua):

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

  • Аналогичное магическое число для числа одиночной точности: 1.5 * 2 ^23

Ответы

Ответ 1

A double представляется следующим образом:

double representation

и это можно рассматривать как два 32-битных целых числа; теперь int, взятый во всех версиях вашего кода (предположим, что это 32-разрядный int) - тот, что справа на рисунке, поэтому то, что вы делаете в конце, просто принимает самые младшие 32 бита мантиссы.

Теперь, к магическому числу; как вы правильно заявили, 6755399441055744 составляет 2 ^ 51 + 2 ^ 52; добавление такого числа заставляет double перейти в "сладкий диапазон" между 2 ^ 52 и 2 ^ 53, что, как объясняется Wikipedia здесь, имеет интересное свойство:

Между 2 52= 4,503,599,627,370,496 и 2 53= 9,007,199,254,740,992 представляемые числа являются целыми числами

Это следует из того, что мантисса имеет ширину 52 бит.

Другой интересный факт о добавлении 2 51 +2 52 заключается в том, что он влияет на мантиссу только на два старших бита, которые все равно отбрасываются, поскольку мы принимаем только его младшие 32 бит.

И последнее, но не менее важное: знак.

Плавающая точка IEEE 754 использует представление величины и знака, в то время как целые числа на "нормальных" машинах используют 2-мерную арифметику; как это обрабатывается здесь?

Мы говорили только о положительных целых числах; теперь предположим, что мы имеем дело с отрицательным числом в диапазоне, представляемом 32-битным int, поэтому меньше (по абсолютной величине), чем (-2 ^ 31 + 1); назовите его -a. Такое число очевидно положительно, добавляя магическое число, а результирующее значение 2 52 +2 51 + (- a).

Теперь, что мы получим, если интерпретировать мантиссу в представлении с двумя дополнениями? Это должно быть результатом 2 дополняющей суммы (2 52 +2 51 ) и (-a). Опять же, первый член влияет только на верхние два бита, то, что остается в битах 0 ~ 50, является 2-дополняющим представлением (-a) (опять же, минус верхние два бита).

Так как уменьшение числа двух дополнений до меньшей ширины выполняется просто путем отсечения лишних битов слева, взятие младших 32 бит дает нам правильную (-a) в 32-битной, 2-арифметической арифметике.