Быстрый метод для округления двойного до 32-битного int
При чтении исходного кода Lua я заметил, что Lua использует macro для округления до 32-битного int . Я извлек macro , и он выглядит так:
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];}
Здесь ENDIANLOC определяется как endianness , 0 для little endian, 1 для большого endian. Lua тщательно обрабатывает сущность. t обозначает целочисленный тип, например int или unsigned int .
Я сделал небольшое исследование, и есть более простой формат macro который использует ту же мысль:
- Каков самый быстрый способ конвертировать float в int на x86
- Какова максимальная длина в символах, необходимых для представления любого двойного значения?
- Преобразование double / float в строку
- Является ли добавление и умножение с плавающей запятой ассоциативным?
- Почему деление двух целых чисел возвращает 0.0 в Java?
#define double2int(i, d) \ {double t = ((d) + 6755399441055744.0); i = *((int *)(&t));}
Или в стиле C ++:
inline int double2int(double d) { d += 6755399441055744.0; return reinterpret_cast(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-битное целое число, ну, я проиграл здесь. Как этот трюк работает?
PS: Это в исходном коде Lua, Llimits.h .
ОБНОВЛЕНИЕ :
- Как отмечает @Mysticial, этот метод не ограничивается 32-битным
int, его также можно развернуть до 64-битногоintпока число находится в диапазоне 2 ^ 52. (macroнуждается в некоторой модификации.) - Некоторые материалы говорят, что этот метод не может использоваться в Direct3D .
-
При работе с ассемблером Microsoft для x86 в
assemblyвыполняется еще более быстрыйmacro(это также извлекается из источника Lua):#define double2int(i,n) __asm {__asm fld n __asm fistp i} -
Существует аналогичное магическое число для единственного числа точности:
1.5 * 2 ^23
- Преобразовать float в строку с заданной точностью и количеством десятичных цифр?
- Как вы печатаете EXACT значение числа с плавающей запятой?
- Алгоритм преобразования двоичного кода IEEE 754 в строку?
- C #: преобразовать массив байтов в float
- Почему 24.0000 не равно 24.0000 в MATLAB?
- Разница между десятичной, плавающей и двойной в .NET?
- pow (), кажется, отсутствует здесь
- Сколько значимых цифр имеет float и double в java?
double выглядит следующим образом:
и это можно рассматривать как два 32-битных целых числа; теперь int взятый во всех версиях вашего кода (предположим, что это 32-битный int ) – тот, что справа на рисунке, поэтому то, что вы делаете в конце, просто берет самые низкие 32 бита мантиссы.
Теперь, к волшебному числу; как вы правильно заявили, 6755399441055744 составляет 2 ^ 51 + 2 ^ 52; добавление такого числа заставляет double перейти в «сладкий диапазон» между 2 ^ 52 и 2 ^ 53, что, как объяснено в Википедии, имеет интересное свойство:
Между 2 52 = 4 503 599 627 370 496 и 2 53 = 9 007 199 994 740 992 представляемые числа – это целые числа
Это следует из того, что мантисса шириной 52 бита.
Другой интересный факт о добавлении 2 51 +2 52 состоит в том, что он влияет на мантиссу только на два старших бита, которые в любом случае отбрасываются, поскольку мы берем только самые младшие 32 бита.
И последнее, но не менее важное: знак.
Плавающая точка IEEE 754 использует представление величины и знака, а целые числа на «нормальных» машинах используют арифметику дополнения 2; как это обрабатывается здесь?
Мы говорили только о положительных целых числах; теперь предположим, что мы имеем дело с отрицательным числом в диапазоне, представимом 32-битным int , поэтому меньше (по абсолютной величине), чем (-2 ^ 31 + 1); назовите его -a . Такое число, очевидно, сделалось положительным, добавив магическое число, а результирующее значение равно 2 52 +2 51 + (- a).
Итак, что мы получим, если интерпретировать мантиссу в представлении о дополнении 2? Это должно быть результатом дополняющей суммы 2 (2 52 +2 51 ) и (-a). Опять же, первый член влияет только на верхние два бита, то, что остается в битах 0 ~ 50, является дополнительным представлением 2 (-a) (опять же, минус верхние два бита).
Поскольку уменьшение числа дополнений 2 до меньшей ширины выполняется просто путем отсечения лишних бит слева, взятие младших 32 бит дает нам правильную (-a) в 32 бит, арифметику дополнений 2.