How to check if float can be exactly represented a

问题:

I'm looking to for a reasonably efficient way of determining if a floating point value (double) can be exactly represented by an integer data type (long, 64 bit).

My initial thought was to check the exponent to see if it was 0 (or more precisely 127). But that won't work because 2.0 would be e=1 m=1...

So basically, I am stuck. I have a feeling that I can do this with bit masks, but I'm just not getting my head around how to do that at this point.

So how can I check to see if a double is exactly representable as a long?

Thanks

回答1:

Here's one method that could work in most cases. I'm not sure if/how it will break if you give it NaN, INF, very large (overflow) numbers...
(Though I think they will all return false - not exactly representable.)

You could:

1. Cast it to an integer.
2. Cast it back to a floating-point.
3. Compare with original value.

Something like this:

double val = ... ;  //  Value

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

floor() and ceil() are also fair game (though they may fail if the value overflows an integer):

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

---

And here's a messy bit-mask solution:
This uses union type-punning and assumes IEEE double-precision. Union type-punning is only valid in C99 TR2 and later.

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

回答2:

I think I have found a way to clamp a double into an integer in a standard-conforming fashion (this is not really what the question is about, but it helps a lot). First, we need to see why the obvious code is not correct.

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

The problem here is that in the second comparison, UINT64_MAX is being implicitly converted to double. The C standard does not specify exactly how this conversion works, only that it is to be rounded up or down to a representable value. This means that the second comparison may be false, even if should mathematically be true (which can happen when UINT64_MAX is rounded up, and 'x' is mathematically between UINT64_MAX and (double)UINT64_MAX). As such, the conversion of double to uint64_t can result in undefined behavior in that edge case.

Surprisingly, the solution is very simple. Consider that while UINT64_MAX may not be exactly representable in a double, UINT64_MAX+1, being a power of two (and not too large), certainly is. So, if we first round the input to an integer, the comparison x > UINT64_MAX is equivalent to x >= UINT64_MAX+1, except for possible overflow in the addition. We can fix the overflow by using ldexp instead of adding one to UINT64_MAX. That being said, the following code should be correct.

/* 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;
}

Now, to back to your question: is x is exactly representable in an uint64_t? Only if it was neither rounded nor clamped.

/* 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));
}

The same algorithm can be used for integers of different size, and also for signed integers with a minor modification. The code that follows does some very basic tests of the uint32_t and uint64_t versions (only false positives can possibly be caught), but is also suitable for manual examination of the edge cases.

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

回答3:

You can use the modf function to split a float into the integer and fraction parts. modf is in the standard C library.

#include <math.h>
#include <limits.h>   

double val = ...
double i;
long l;

/* check if fractional part is 0 */
if (modf(val, &i) == 0.0) {
    /* val is an integer. check if it can be stored in a long */
    if (val >= LONG_MIN && val <= LONG_MAX) {
        /* can be exactly represented by a long */
        l = val;
    }
}

回答4:

How to check if float can be exactly represented as an integer ?

I'm looking to for a reasonably efficient way of determining if a floating point value double can be exactly represented by an integer data type long, 64 bit.

Range (LONG_MIN, LONG_MAX) and fraction (frexp()) tests needed. Also need to watch out for not-a-numbers.

---

The usual idea is to test like (double)(long)x == x, but to avoid its direct usage. (long)x, when x is out of range, is undefined behavior (UB).

The valid range of conversion for (long)x is LONG_MIN - 1 < x < LONG_MAX + 1 as code discards any fractional part of x during the conversion. So code needs to test, using FP math, if x is in range.

#include <limits.h>
#include <stdbool.h>
#define DBL_LONG_MAXP1 (2.0*(LONG_MAX/2+1)) 
#define DBL_LONG_MINM1 (2.0*(LONG_MIN/2-1)) 

bool double_to_long_exact_possible(double x) {
  if (x < DBL_LONG_MAXP1) {
    double whole_number_part;
    if (frexp(x, &whole_number_part) != 0.0) {
      return false;  // Fractional part exist.
    }
    #if -LONG_MAX == LONG_MIN
    // rare non-2's complement machine 
    return x > DBL_LONG_MINM1;
    #else
    return x - LONG_MIN > -1.0;
    #endif 
  }
  return false;  // Too large or NaN
}

回答5:

Any IEEE floating-point double or float value with a magnitude at or above 2^52 or 2^23 will be whole number. Adding 2^52 or 2^23 to a positive number whose magnitude is less than that will cause it to be rounded to a whole number. Subtracting the value that was added will yield a whole number which will equal the original iff the original was a whole number. Note that this algorithm will fail with some numbers larger than 2^52, but it isn't needed for numbers that big.

回答6:

Could you use the modulus operator to check if the double is divisible by one... or am I completely misunderstanding the question?

double val = ... ;  //  Value

if(val % 1 == 0) {
    // Val is evenly divisible by 1 and is therefore a whole number
}