CODEWITHSUNDEEP
c++clanguage-lawyerdistance
Öö Tiib
Öö Tiib

Reputation: 10979

distance between two signed numbers

The distance between two numbers is often calculated like that:

long distance(long x, long y)
{
     return x > y ? x - y : y - x;
}

However with signed x and y these subtractions there may overflow and so that function can invoke undefined behavior both in C and C++.

One way out of that issue is to use unsigned type to represent resulting distance. Distance can not be negative so signed type is not needed. Distance between minimum and maximum of signed type should fit into unsigned type of same size. (Edit: As chux answered it was not entirely correct assumption.) So I did modify the first function like that:

unsigned long distance(long x, long y)
{
    return (x > y) ? (unsigned long)x - (unsigned long)y
                   : (unsigned long)y - (unsigned long)x;
}

Does it now correctly calculate the distance between two signed longs in standard conforming and portable manner? If it does not, what would be the fix?

Upvotes: 6

Views: 1878

Answers (3)

0___________
0___________

Reputation: 67476

assuming sizeof(unsigned long long) > sizeof(unsigned long) it safe to declare it as : unsigned long long distance(long x, long y)

but because nowadays ones complement or another exotic format number are not in a common use (actually it is very unlikely anyone to have an opportunity to code C on such a machines) the unsigned long type can accommodate all possible distances.

Upvotes: -1

chux
chux

Reputation: 153338

Does it now correctly calculate the distance between two signed longs in standard conforming and portable manner?

Yes.

Rare exception1 would oblige using a wider type.

Consider the 3 cases when x > y

x >= 0, y >= 0

Following is trivially correct as the cast does not change value.

(unsigned long)x - (unsigned long)y

x < 0, y < 0

Both x,y values are increased by ULONG_MAX + 1 due to the (unsigned long) and the subtraction cancels that out.

// is akin to 
((unsigned long)(x + ULONG_MAX + 1) - (unsigned long)(y + ULONG_MAX + 1))
// or
x - y // with unsigned math.

x >= 0, y < 0

(unsigned long)y has the value of y + ULONG_MAX + 1, which is more than x. (Assuming ULONG_MAX/2 >= LONG_MAX1) The difference is negative. Yet unsigned math wraps around, and adds back ULONG_MAX + 1.

// is akin to 
((unsigned long)x - (unsigned long)(y + ULONG_MAX + 1)) + (ULONG_MAX + 1).
// or
x - y // with unsigned math.

x < 0, y >= 0

This case not possible as x > y.

1: C does not specify ULONG_MAX/2 == LONG_MAX even though that is exceedingly common. I've only come across this once long ago where it did not apply. It that case it was ULONG_MAX == LONG_MAX. ULONG_MAX/2 == LONG_MAX is so expected that I doubt a modern platform would risk not doing so. C does specify ULONG_MAX >= LONG_MAX.

The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the representation of the same value in each type is the same. ... C11dr §6.2.5 9

Code could use the below to detect these rare platforms.

#if ULONG_MAX/2 < LONG_MAX
  #error `unsigned long` too narrow.  Need new approach.
#endif

Upvotes: 9

izac89
izac89

Reputation: 3930

Since unsigned overflow (and underflow) is well defined for C and C++, when 2's complement arithmetic is used your modified function is perfectly fine.

Upvotes: 0

Related Questions