더블을 32비트 int로 반올림하는 빠른 방법

더블을 32비트 int로 반올림하는 빠른 방법

Lua의 소스 코드를 읽었을 때, Lua가 매크로를 사용하여 반올림하는 것을 발견했습니다.double 32비트 값int가치.매크로는 헤더 파일에 정의되어 있으며 다음과 같이 읽힙니다.

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

서 ★★★★ENDIANLOCendianness에 따라 정의됩니다.little endian의 경우 0, big endian 아키텍처의 경우 1입니다.Lua는 endianness를 신중하게 처리합니다.그t는 ''와 같은 됩니다.int ★★★★★★★★★★★★★★★★★」unsigned int.

조금 조사해 보니, 같은 기술을 사용하는 매크로의 단순한 형식이 있습니다.

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

또는 C++ 스타일의 경우:

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★★★★★★ 。

저는 이 까다로운 매크로가 어떻게 작동하는지 자세히 알고 싶습니다. 넘버 ★★★★★★★★★★★★★★★★6755399441055744.0는 실제로는⁵¹ 2+2⁵², 즉 1.5×2⁵², 바이너리에서는 1.5를 1.1로 나타낼 수 있습니다.32비트 정수가 이 매직넘버에 추가되었을 경우:

글쎄, 난 여기서 길을 잃었어.이 속임수는 어떻게 작동하나요?

갱신하다

1. @한 바와 같이@Mysticial에 .int 64비트까지 도 있습니다.int(단, 매크로의 수정이 필요하지만) 숫자가 2의 범위에⁵² 있는 한.

2. 일부 소재는 Direct3D에서 이 방식을 사용할 수 없다고 밝히고 있다.

3. x86용 Microsoft 어셈블러를 사용하면 어셈블리 코드로 작성된 보다 빠른 매크로가 있습니다(다음은 Lua 소스에서도 추출됩니다).

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

4. 단일 정밀도 숫자에 대해서도 유사한 매직 번호가 있습니다. 1.5 × 2입니다²³.

의 값double부동소수점 유형은 다음과 같이 표시됩니다.

정수로 볼수 2는 32비트 정수로 볼 수 있습니다.int의 코드로 버전인 int그림에서는 오른쪽이 오른쪽이므로 맨 아래 32비트의 가수만 추출합니다.bits의 가수입니다.

---

이제 매직넘버에 대해서 설명하겠습니다.정확하게 말한 대로 6755399441055744는 2+2입니다⁵¹⁵².이러한 수치를 더하면,doubleWikipedia에서 설명한 바와 같이 "sweet range"에⁵²⁵³ 들어가는 것은 흥미로운 특성을 가지고 있습니다.

2 = 4,503,599,627,496 및 2⁵³ = 9,007,199,254,740,992 사이에서 표현 가능한⁵² 숫자는 정확히 정수입니다.

이는 사마귀의 폭이 52비트라는 사실에서 비롯됩니다.

2 + 2를⁵² 더하는⁵¹ 것에 관한 또 다른 흥미로운 사실은 가장 높은 2비트의 가수에만 영향을 미친다는 것입니다.그것은 어쨌든 폐기됩니다.이는 최하위 32비트만 취하기 때문입니다.

---

마지막이지만 가장 중요한 것은 표지판입니다.

IEEE 754 부동소수점에서는 매그니튜드와 부호표현을 사용하는 반면, "일반" 기계에서는 정수가 2의 보완산술을 사용합니다.여기서는 어떻게 처리합니까?

의 '정수'로 수 있는 해 보겠습니다.이제 32비트로 나타낼 수 있는 범위의 음수를 다루고 있다고 가정합니다.int따라서³¹ (절대값으로) (-2 + 1)보다 작습니다. -a라고 부릅니다.이러한 숫자는 매직 넘버를 더하면 분명히 양수가 되고, 결과값은 2 + 2⁵¹ + (-a)가 됩니다⁵².

이제 2의 보형 표현으로 가수들을 해석하면 어떤 결과를 얻을 수 있을까요?2의 보합이 (2⁵² + 2⁵¹)와 (-a)인 결과여야 합니다.첫 번째 항은 상위 2비트에만 영향을 줍니다. 비트 0 ~ 50에 남아 있는 것은 2의 보완 표현(-a)입니다(이것도 마찬가지로 상위 2비트를 뺀 값입니다).

왼쪽의 여분의 비트를 잘라내는 것만으로 2의 보수를 작은 폭으로 줄일 수 있기 때문에 하위 32비트를 취하면 32비트 2의 보수를 정확하게 계산할 수 있습니다.

이러한 "꼼수"는 8087 명령/인터페이스를 부동소수로 사용하는 오래된 x86 프로세서에서 비롯됩니다.이러한 기계에서는 부동소수를 정수 "fist"로 변환하는 명령이 있지만 현재 fp 반올림 모드를 사용합니다. 변환은 0을 은 가장 fp 연산으로 int fp->int > 를 실행합니다.
fp->int 변환에서는 먼저 fp 반올림 모드를 변경한 후 fp 반올림 모드를 복원해야 합니다.

원래 8086/8087에서는 그다지 나쁘지 않았습니다만, 슈퍼 스칼라나 잘못된 실행이 시작된 이후의 프로세서에서는 fp 반올림 모드를 변경하면 일반적으로 CPU 코어가 시리얼화되어 매우 고가입니다.따라서 Pentium-III 또는 Pentium-IV와 같은 CPU에서는 이 전체 비용이 상당히 높습니다.일반적인 fp->int 변환은 이 add+store+load 기술보다 10배 이상 비쌉니다.

단, x86-64에서는 부동소수는 xmm 명령으로 처리되며 변환 비용은
fp->int는 매우 작기 때문에 이 "최적화"는 일반 변환보다 느릴 수 있습니다.

이것이 시각화에 도움이 된다면, 그 루아 마법의 가치는

  (2^52+2^51, or base2 of 110 then [50 zeros]

16진수

  0x  0018 0000 0000 0000 (18e12)

8진수

  0 300 00000 00000 00000 ( 3e17)

위의 Lua 트릭의 간단한 실장은 다음과 같습니다.

/**
 * Round to the nearest integer.
 * for tie-breaks: round half to even (bankers' rounding)
 * Only works for inputs in the range: [-2^51, 2^51]
 */
inline double rint(double d)
{
    double x = 6755399441055744.0;  // 2^51 + 2^52
    return d + x - x;
}

이 트릭은 절대값이 2 ^ 51 미만인 수치로 동작합니다.

이것은 테스트하기 위한 작은 프로그램입니다.ideone.com

#include <cstdio>

int main()
{
    // round to nearest integer
    printf("%.1f, %.1f\n", rint(-12345678.3), rint(-12345678.9));

    // test tie-breaking rule
    printf("%.1f, %.1f, %.1f, %.1f\n", rint(-24.5), rint(-23.5), rint(23.5), rint(24.5));      
    return 0;
}

// output:
// -12345678.0, -12345679.0
// -24.0, -24.0, 24.0, 24.0

언급URL : https://stackoverflow.com/questions/17035464/a-fast-method-to-round-a-double-to-a-32-bit-int-explained