distance between two signed numbers

  • A+
Category:Languages

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?

 


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 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: