CODEWITHSUNDEEP
cfloating-pointcomparison
user4259083
user4259083

Reputation:

Compare floating point numbers as integers

Can two floating point values (IEEE 754 binary64) be compared as integers? Eg.

long long a = * (long long *) ptr_to_double1,
          b = * (long long *) ptr_to_double2;
if (a < b) {...}

assuming the size of long long and double is the same.

Upvotes: 8

Views: 5565

Answers (3)

Dave Dopson
Dave Dopson

Reputation: 42716

YES - Comparing the bit-patterns for two floats as if they were integers (aka "type-punning") produces meaningful results under some restricted scenarios...

Identical to floating-point comparison when:

  • Both numbers are positive, positive-zero, or positive-infinity.
  • One positive and one negative number, and you are using a signed integer comparison.

Inverse of floating-point comparison when:

  • Both numbers are negative, negative-zero, or negative-infinity.
  • One positive and one negative number, and you are using a unsigned integer comparison.

Not comparable to floating-point comparison when:

  • Either number is one of the NaN values - Floating point comparisons with a NaN always returns false, and this simply can't be modeled in integer operations where exactly one of the following is always true: (A < B), (A == B), (B < A).

Negative floating-point numbers are a bit funky b/c they are handled very differently than in the 2's complement arithmetic used for integers. Doing an integer +1 on the representation for a negative float will make it a bigger negative number.

With a little bit manipulation, you can make both positive and negative floats comparable with integer operations (this can come in handy for some optimizations):

int32 float_to_comparable_integer(float f) {
  uint32 bits = std::bit_cast<uint32>(f);
  const uint32 sign_bit = bits & 0x80000000ul;
  // Modern compilers turn this IF-statement into a conditional move (CMOV) on x86,
  // which is much faster than a branch that the cpu might mis-predict.
  if (sign_bit) {
    // Negative values from [0x00000001, 0x7F7FFFFF]
    bits = 0xFF800000 - bits;
  } else {
    // Positive values from [0x7FFFFFFF, 0xFF7FFFFF]
    bits = 0x7FFFFFFF + bits;
  }
  return static_cast<int32>(bits);
}

Tested here: https://godbolt.org/z/WEYTGEqqs

Again, this technique only works when none of the values are NaN. It's impossible for integer comparisons to reproduce IEEE-754's NaN comparison behavior of producing false for all comparisons where either side of the comparison has one of the following NaN bit patterns:

  • Signaling NaNs (w/ sign bit): Anything between 0xFF800001, and 0xFFBFFFFF.
  • Signaling NaNs (w/o sign bit): Anything between 0x7F800001, and 0x7FBFFFFF.
  • Quiet NaNs (w/ sign bit): Anything between 0xFFC00000, and 0xFFFFFFFF.
  • Quiet NaNs (w/o sign bit): Anything between 0x7FC00000, and 0x7FFFFFFF.

IEEE-754 bit format: http://www.puntoflotante.net/FLOATING-POINT-FORMAT-IEEE-754.htm

More on Type-Punning: https://randomascii.wordpress.com/2012/01/23/stupid-float-tricks-2/

Upvotes: 17

chux
chux

Reputation: 154174

No. Two floating point values (IEEE 754 binary64) cannot compare simply as integers with if (a < b).

IEEE 754 binary64

The order of the values of double is not the same order as integers (unless you are are on a rare sign-magnitude machine). Think positive vs. negative numbers.

double has values like 0.0 and -0.0 which have the same value but different bit patterns.

double has "Not-a-number"s that do not compare like their binary equivalent integer representation.

If both the double values were x > 0 and not "Not-a-number", endian, aliasing, and alignment, etc. were not an issue, OP's idea would work.

Alternatively, a more complex if() ... condition would work - see below

[non-IEEE 754 binary64]

Some double use an encoding where there are multiple representations of the same value. This would differ from an "integer" compare.

Tested code: needs 2's complement, same endian for double and the integers, does not account for NaN.

int compare(double a, double b) {
  union {
    double d;
    int64_t i64;
    uint64_t u64;
  } ua, ub;
  ua.d = a;
  ub.d = b;
  // Cope with -0.0 right away
  if (ua.u64 == 0x8000000000000000) ua.u64 = 0;
  if (ub.u64 == 0x8000000000000000) ub.u64 = 0;
  // Signs differ?
  if ((ua.i64 < 0) != (ub.i64 < 0)) {
    return ua.i64 >= 0 ? 1 : -1;
  }
  // If numbers are negative
  if (ua.i64 < 0) {
    ua.u64 = -ua.u64;
    ub.u64 = -ub.u64;
  }
  return (ua.u64 > ub.u64)  - (ua.u64 < ub.u64);
}

Thanks to @David C. Rankin for a correction.

Test code

void testcmp(double a, double b) {
  int t1 = (a > b) - (a < b);
  int t2 = compare(a, b);
  if (t1 != t2) {
    printf("%le %le %d %d\n", a, b, t1, t2);
  }

}

#include <float.h>
void testcmps() {
  // Various interesting `double`
  static const double a[] = { 
      -1.0 / 0.0, -DBL_MAX, -1.0, -DBL_MIN, -0.0, 
      +0.0, DBL_MIN, 1.0, DBL_MAX, +1.0 / 0.0 };

  int n = sizeof a / sizeof a[0];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      testcmp(a[i], a[j]);
    }
  }
  puts("!");
}

Upvotes: 4

Steve Hollasch
Steve Hollasch

Reputation: 2131

If you strictly cast the bit value of a floating point number to its correspondingly-sized signed integer (as you've done), then signed integer comparison of the results will be identical to the comparison of the original floating-point values, excluding NaN values. Put another way, this comparison is legitimate for all representable finite and infinite numeric values.

In other words, for double-precision (64-bits), this comparison will be valid if the following tests pass:

long long exponentMask = 0x7ff0000000000000;
long long mantissaMask = 0x000fffffffffffff;

bool isNumber =  ((x & exponentMask) != exponentMask)  // Not exp 0x7ff
              || ((x & mantissaMask) == 0);            // Infinities

for each operand x.

Of course, if you can pre-qualify your floating-point values, then a quick isNaN() test would be much more clear. You'd have to profile to understand performance implications.

Upvotes: -1

Related Questions