12

我们的服务器应用程序在热代码路径中进行了大量的整数测试，目前我们使用以下函数：

inline int IsInteger(double n)
{
    return n-floor(n) < 1e-8
}

这个功能在我们的工作量中非常热门，所以我希望它尽可能快。如果可以的话，我还想消除“地板”库调用。有什么建议么？

4

5 回答 5

11

这里有几个答案：

#include <stdint.h>
#include <stdio.h>
#include <math.h>

int IsInteger1(double n)
{
  union
  {
        uint64_t i;
        double d;
  } u;
  u.d = n;

  int exponent = ((u.i >> 52) & 0x7FF) - 1023;
  uint64_t mantissa = (u.i & 0x000FFFFFFFFFFFFFllu);

  return n == 0.0 ||
        exponent >= 52 ||
        (exponent >= 0 && (mantissa << (12 + exponent)) == 0);
}

int IsInteger2(double n)
{
  return n - (double)(int)n == 0.0;
}

int IsInteger3(double n)
{
  return n - floor(n) == 0.0;
}

和一个测试工具：

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int IsInteger1(double);
int IsInteger2(double);
int IsInteger3(double);

#define TIMEIT(expr, N) \
  gettimeofday(&start, NULL); \
  for(i = 0; i < N; i++) \
  { \
    expr; \
  } \
  gettimeofday(&end, NULL); \
  printf("%s: %f\n", #expr, (end.tv_sec - start.tv_sec) + 0.000001 * (end.tv_usec - start.tv_usec))

int main(int argc, char **argv)
{
  const int N = 100000000;
  struct timeval start, end;
  int i;

  double d = strtod(argv[1], NULL);
  printf("d=%lf %d %d %d\n", d, IsInteger(d), IsInteger2(d), IsInteger3(d));

  TIMEIT((void)0, N);
  TIMEIT(IsInteger1(d), N);
  TIMEIT(IsInteger2(d), N);
  TIMEIT(IsInteger3(d), N);

  return 0;
}

编译为：

gcc isinteger.c -O3 -c -o isinteger.o
gcc main.c isinteger.o -o isinteger

我在 Intel Core Duo 上的结果：

$ ./isinteger 12345
d=12345.000000 1 1 1
(void)0: 0.357215
IsInteger1(d): 2.017716
IsInteger2(d): 1.158590
IsInteger3(d): 2.746216

结论：旋转的速度并不像我想象的那么快。额外的分支可能是杀死它的原因，即使它避免了浮点运算。如今，FPU 的速度已经足够快，以至于进行double转换int或转换floor并没有那么慢。

于 2009-12-22T05:38:23.533 回答
9

不久前，我对在浮点数和整数之间进行转换的最有效方法进行了一系列计时，并将它们写下来。我还计时了四舍五入的技巧。

简短的故事是：从浮点数转换为整数，或使用联合黑客，由于称为加载命中存储的 CPU 危害，不太可能得到改进——除非浮点数来自 RAM 而不是登记。

因为它是一个内在函数，所以 abs(floor(x)-eps) 可能是最快的解决方案。但是因为这对你的 CPU 的特定架构非常敏感——取决于非常敏感的东西，比如管道深度和存储转发——你需要对各种解决方案进行计时，以找到一个真正最佳的解决方案。

于 2009-12-22T05:56:33.403 回答
4

如果double您机器上的 s 符合 IEEE-754 标准，则此联合描述了双精度的布局。

union
{
   double d;
   struct
   {
       int sign     :1
       int exponent :11
       int mantissa :52
   };
} double_breakdown;

这将告诉您 double 是否代表整数。

免责声明 1：我说的是integer，而不是int，因为 double 可以表示整数，但其幅度太大而无法存储在int.

免责声明 2：双打将保持最接近任何实数的可能值。所以这只能返回所表示的数字是否形成整数。例如，非常大的双精度数总是整数，因为它们没有足够的有效数字来表示任何小数值。

bool is_integer( double d )
{
    const int exponent_offset = 1023;
    const int mantissa_bits = 52;

    double_breakdown *db = &d;

    // See if exponent is too large to hold a decimal value.
    if ( db->exponent >= exponent_offset + mantissa_bits )
       return true;  // d can't represent non-integers

    // See if exponent is too small to hold a magnitude greater than 1.0.
    if ( db->exponent <= exponent_offset )
       return false; // d can't represent integers

    // Return whether any mantissa bits below the decimal point are set.
    return ( db->mantissa << db->exponent - exponent_offset == 0 );
}
于 2009-12-22T04:44:28.323 回答
0

另一种选择：

inline int IsInteger(double n)
{
    double dummy;
    return modf(n, &dummy) == 0.0;
}
于 2009-12-22T06:09:49.063 回答
0

如果您真的想变得 hackish，请参阅IEEE 754规范。浮点数被实现为有效数和指数。我不确定到底该怎么做，但你可能会做类似的事情：

union {
    float f;
    unsigned int i;
}

这将使您可以按位访问有效数和指数。然后你就可以绕圈子了。

于 2009-12-22T04:23:23.013 回答