如何检查float是否可以精确表示为整数

Question

我正在寻找一种合理有效的方法来确定浮点值(double)是否可以由整数数据类型(long,64位)精确表示.

我最初的想法是检查指数是否0(或更确切地说127).但这不会起作用,因为2.0e = 1 m = 1 ......

基本上,我被卡住了.我有一种感觉,我可以使用位掩码做到这一点,但我现在还没有理解如何做到这一点.

那么我怎样才能检查一个double是否完全可以表示为long？

谢谢

Answer 1

这是一种在大多数情况下都可以使用的方法.我不确定如果你给它NaN,它是否会/如何破坏INF,非常大(溢出)的数字...
(虽然我认为它们都将返回假 - 不完全可以表示.)

你可以:

1. 将其转换为整数.
2. 把它扔回浮点.
3. 与原始值比较.

像这样的东西:

double val = ... ;  //  Value

if ((double)(long long)val == val){
    //  Exactly representable
}

floor()并且ceil()也是公平的游戏(尽管如果值溢出整数,它们可能会失败):

floor(val) == val
ceil(val) == val

这里是一个凌乱的位掩码解决方案:
它使用union类型 - 双精度并假设IEEE双精度.联合类型 - 惩罚仅在C99 TR2及更高版本中有效.

int representable(double x){
    //  Handle corner cases:
    if (x == 0)
      return 1;

    //  -2^63 is representable as a signed 64-bit integer, but +2^63 is not.
    if (x == -9223372036854775808.)
      return 1;

    //  Warning: Union type-punning is only valid in C99 TR2 or later.
    union{
        double f;
        uint64_t i;
    } val;

    val.f = x;

    uint64_t exp = val.i & 0x7ff0000000000000ull;
    uint64_t man = val.i & 0x000fffffffffffffull;
    man |= 0x0010000000000000ull;  //  Implicit leading 1-bit.

    int shift = (exp >> 52) - 1075;
    //  Out of range
    if (shift < -52 || shift > 10)
        return 0;

    //  Test mantissa
    if (shift < 0){
        shift = -shift;
        return ((man >> shift) << shift) == man;
    }else{
        return ((man << shift) >> shift) == man;
    }
}

Answer 2

我想我已经找到了一种方法,以double符合标准的方式将一个整数钳入一个整数(这不是真正的问题,但它有很多帮助).首先,我们需要了解为什么明显的代码不正确.

// INCORRECT CODE
uint64_t double_to_uint64 (double x)
{
    if (x < 0.0) {
        return 0;
    }
    if (x > UINT64_MAX) {
        return UINT64_MAX;
    }
    return x;
}

这里的问题是在第二次比较中,UINT64_MAX被隐式转换为double.C标准没有详细说明此转换的工作原理,只是将其向上舍入或向下舍入为可表示的值.这意味着第二次比较可能是错误的,即使在数学上应该是真的(这可以在UINT64_MAX向上舍入时发生,并且'x'在数学上在UINT64_MAX和之间(double)UINT64_MAX).因此,doubleto 的转换uint64_t可能导致该边缘情况下的未定义行为.

令人惊讶的是,解决方案非常简单.想想看,虽然UINT64_MAX可能不是一个精确表示double,UINT64_MAX+1,是两个(而不是过大)的功率,肯定是.因此,如果我们首先将输入舍入为整数,则比较x > UINT64_MAX等效x >= UINT64_MAX+1,除了可能的加法溢出.我们可以通过使用ldexp而不是添加一个来修复溢出UINT64_MAX.话虽如此,以下代码应该是正确的.

/* Input: a double 'x', which must not be NaN.
 * Output: If 'x' is lesser than zero, then zero;
 *         otherwise, if 'x' is greater than UINT64_MAX, then UINT64_MAX;
 *         otherwise, 'x', rounded down to an integer.
 */
uint64_t double_to_uint64 (double x)
{
    assert(!isnan(x));
    double y = floor(x);
    if (y < 0.0) {
        return 0;
    }
    if (y >= ldexp(1.0, 64)) {
        return UINT64_MAX;
    }
    return y;
}

现在,回到你的问题:x是否完全可以代表uint64_t？只有它既不是圆形也不是夹紧的.

/* Input: a double 'x', which must not be NaN.
 * Output: If 'x' is exactly representable in an uint64_t,
 *         then 1, otherwise 0.
 */
int double_representable_in_uint64 (double x)
{
    assert(!isnan(x));
    return (floor(x) == x && x >= 0.0 && x < ldexp(1.0, 64));
}

相同的算法可以用于不同大小的整数,也可以用于具有微小修改的有符号整数.下面的代码对uint32_t和uint64_t版本进行了一些非常基本的测试(只能捕获误报),但也适用于边缘情况的手动检查.

#include <inttypes.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <stdio.h>

uint32_t double_to_uint32 (double x)
{
    assert(!isnan(x));
    double y = floor(x);
    if (y < 0.0) {
        return 0;
    }
    if (y >= ldexp(1.0, 32)) {
        return UINT32_MAX;
    }
    return y;
}

uint64_t double_to_uint64 (double x)
{
    assert(!isnan(x));
    double y = floor(x);
    if (y < 0.0) {
        return 0;
    }
    if (y >= ldexp(1.0, 64)) {
        return UINT64_MAX;
    }
    return y;
}

int double_representable_in_uint32 (double x)
{
    assert(!isnan(x));
    return (floor(x) == x && x >= 0.0 && x < ldexp(1.0, 32));
}

int double_representable_in_uint64 (double x)
{
    assert(!isnan(x));
    return (floor(x) == x && x >= 0.0 && x < ldexp(1.0, 64));
}

int main ()
{
    {
        printf("Testing 32-bit\n");
        for (double x = 4294967295.999990; x < 4294967296.000017; x = nextafter(x, INFINITY)) {
            uint32_t y = double_to_uint32(x);
            int representable = double_representable_in_uint32(x);
            printf("%f -> %" PRIu32 " representable=%d\n", x, y, representable);
            assert(!representable || (double)(uint32_t)x == x);
        }
    }
    {
        printf("Testing 64-bit\n");
        double x = ldexp(1.0, 64) - 40000.0;
        for (double x = 18446744073709510656.0; x < 18446744073709629440.0; x = nextafter(x, INFINITY)) {
            uint64_t y = double_to_uint64(x);
            int representable = double_representable_in_uint64(x);
            printf("%f -> %" PRIu64 " representable=%d\n", x, y, representable);
            assert(!representable || (double)(uint64_t)x == x);
        }
    }
}