Calculation of integer absolute differences in overflow methods?

Question

I would like to calculate the absolute difference of two integers. Naively, it's just abs(a - b) . However, this has several problems, depending on whether the integers are signed or not:

• For unsigned integers, a - b will be a large positive number if b greater than a , and an absolute value operation will not correct this.

• For signed integers a - b may be outside the range of values ​​that can be represented as a signed integer, which leads to undefined behavior. (Obviously, this means the result must be an unsigned integer.)

How can these problems be effectively addressed?

I need an algorithm (or a couple of algorithms) that works for both signed and unsigned integers, and does not rely on the values ​​being larger.

(In addition, to clarify: my question is not how to write this in code, but what exactly should I write to guarantee security overflow. Calculating abs(a - b) as a signed value, and then casting to an unsigned value does not work, since a signed integer overflow is usually an undefined operation, at least in C.)

Answer 1

(I worked it out myself, asking a question - I thought it would be harder, and I would still welcome other answers if there are better ones!)

The unsigned integer solution is relatively simple (as described in Jack Thule's answer) and works by moving the (implied) conditional out of subtraction, so that we always subtract the smaller number from the larger one and don't compare the potentially wrapped value to zero:

 if (a > b) return a - b; else return b - a; 

This just leaves the question of integers. Consider the following variation:

 if (a > b) return (unsigned) a - (unsigned) b; else return (unsigned) b - (unsigned) a; 

We can easily prove that this works using modulo arithmetic. We know that a and (unsigned) a are congruent modulo UINT_MAX . In addition, an (unsigned) a - (unsigned) b operation corresponds to the actual subtraction modulo UINT_MAX , therefore, combining these facts, we know that (unsigned) a - (unsigned) b corresponds to the actual value a - b modulo UINT_MAX . Finally, since we know that the actual value of a - b must be between 0 and UINT_MAX-1 , we know that this is an exact equality.

Answer 2

Edited to use the Brook Moses fix for signed types and Kerrek SB make_unsigned to allow the use of the template.

First, you can either have the following for make_unsigned, or use std :: make_unsigned, tr1 :: make_unsigned or BOOST :: make_unsigned.

 template <typename T> struct make_unsigned { }; template <> struct make_unsigned<bool > {}; template <> struct make_unsigned< signed short > {typedef unsigned short type;}; template <> struct make_unsigned<unsigned short > {typedef unsigned short type;}; template <> struct make_unsigned< signed int > {typedef unsigned int type;}; template <> struct make_unsigned<unsigned int > {typedef unsigned int type;}; template <> struct make_unsigned< signed long > {typedef unsigned long type;}; template <> struct make_unsigned<unsigned long > {typedef unsigned long type;}; template <> struct make_unsigned< signed long long> {typedef unsigned long long type;}; template <> struct make_unsigned<unsigned long long> {typedef unsigned long long type;}; 

Then the template definition becomes simple:

 template <typename T> typename make_unsigned<T>::type absdiff(T a, T b) { typedef typename make_unsigned<T>::type UT; if (a > b) return static_cast<UT>(a) - static_cast<UT>(b); else return static_cast<UT>(b) - static_cast<UT>(a); } 

As Brooks Moses explains, this protection is safe.

Answer 3

Here is the idea: if we are unsigned, we just accept the right difference. If we signed up, we return the corresponding unsigned type:

 #include <type_traits> template <typename T, bool> struct absdiff_aux; template <typename T> struct absdiff_aux<T, true> { static T absdiff(T a, T b) { return a < b ? b - a : a - b; } }; template <typename T> struct absdiff_aux<T, false> { typedef typename std::make_unsigned<T>::type UT; static UT absdiff(T a, T b) { if ((a > 0 && b > 0) || (a <= 0 && b <= 0)) return { a < b ? b - a : a - b; } if (b > 0) { UT d = -a; return UT(b) + d } else { UT d = -b; return UT(a) + d; } } }; template <typename T> typename std::make_unsigned<T>::type absdiff(T a, T b) { return absdiff_aux<T, std::is_signed<T>::value>::absdiff(a, b); } 

Usage: int a, b; unsigned int d = absdiff(a, b); int a, b; unsigned int d = absdiff(a, b);

Answer 4

the code:

 #include <stdio.h> #include <limits.h> unsigned AbsDiffSigned(int a, int b) { unsigned diff = (unsigned)a - (unsigned)b; if (a < b) diff = 1 + ~diff; return diff; } unsigned AbsDiffUnsigned(unsigned a, unsigned b) { unsigned diff = a - b; if (a < b) diff = 1 + ~diff; return diff; } int testDataSigned[] = { { INT_MIN }, { INT_MIN + 1 }, { -1 }, { 0 }, { 1 }, { INT_MAX - 1 }, { INT_MAX } }; unsigned testDataUnsigned[] = { { 0 }, { 1 }, { UINT_MAX / 2 + 1 }, { UINT_MAX - 1 }, { UINT_MAX } }; int main(void) { int i, j; printf("Absolute difference of signed integers:\n"); for (j = 0; j < sizeof(testDataSigned)/sizeof(testDataSigned[0]); j++) for (i = 0; i < sizeof(testDataSigned)/sizeof(testDataSigned[0]); i++) printf("abs(%d - %d) = %u\n", testDataSigned[j], testDataSigned[i], AbsDiffSigned(testDataSigned[j], testDataSigned[i])); printf("Absolute difference of unsigned integers:\n"); for (j = 0; j < sizeof(testDataUnsigned)/sizeof(testDataUnsigned[0]); j++) for (i = 0; i < sizeof(testDataUnsigned)/sizeof(testDataUnsigned[0]); i++) printf("abs(%u - %u) = %u\n", testDataUnsigned[j], testDataUnsigned[i], AbsDiffUnsigned(testDataUnsigned[j], testDataUnsigned[i])); return 0; } 

Conclusion:

 Absolute difference of signed integers: abs(-2147483648 - -2147483648) = 0 abs(-2147483648 - -2147483647) = 1 abs(-2147483648 - -1) = 2147483647 abs(-2147483648 - 0) = 2147483648 abs(-2147483648 - 1) = 2147483649 abs(-2147483648 - 2147483646) = 4294967294 abs(-2147483648 - 2147483647) = 4294967295 abs(-2147483647 - -2147483648) = 1 abs(-2147483647 - -2147483647) = 0 abs(-2147483647 - -1) = 2147483646 abs(-2147483647 - 0) = 2147483647 abs(-2147483647 - 1) = 2147483648 abs(-2147483647 - 2147483646) = 4294967293 abs(-2147483647 - 2147483647) = 4294967294 abs(-1 - -2147483648) = 2147483647 abs(-1 - -2147483647) = 2147483646 abs(-1 - -1) = 0 abs(-1 - 0) = 1 abs(-1 - 1) = 2 abs(-1 - 2147483646) = 2147483647 abs(-1 - 2147483647) = 2147483648 abs(0 - -2147483648) = 2147483648 abs(0 - -2147483647) = 2147483647 abs(0 - -1) = 1 abs(0 - 0) = 0 abs(0 - 1) = 1 abs(0 - 2147483646) = 2147483646 abs(0 - 2147483647) = 2147483647 abs(1 - -2147483648) = 2147483649 abs(1 - -2147483647) = 2147483648 abs(1 - -1) = 2 abs(1 - 0) = 1 abs(1 - 1) = 0 abs(1 - 2147483646) = 2147483645 abs(1 - 2147483647) = 2147483646 abs(2147483646 - -2147483648) = 4294967294 abs(2147483646 - -2147483647) = 4294967293 abs(2147483646 - -1) = 2147483647 abs(2147483646 - 0) = 2147483646 abs(2147483646 - 1) = 2147483645 abs(2147483646 - 2147483646) = 0 abs(2147483646 - 2147483647) = 1 abs(2147483647 - -2147483648) = 4294967295 abs(2147483647 - -2147483647) = 4294967294 abs(2147483647 - -1) = 2147483648 abs(2147483647 - 0) = 2147483647 abs(2147483647 - 1) = 2147483646 abs(2147483647 - 2147483646) = 1 abs(2147483647 - 2147483647) = 0 Absolute difference of unsigned integers: abs(0 - 0) = 0 abs(0 - 1) = 1 abs(0 - 2147483648) = 2147483648 abs(0 - 4294967294) = 4294967294 abs(0 - 4294967295) = 4294967295 abs(1 - 0) = 1 abs(1 - 1) = 0 abs(1 - 2147483648) = 2147483647 abs(1 - 4294967294) = 4294967293 abs(1 - 4294967295) = 4294967294 abs(2147483648 - 0) = 2147483648 abs(2147483648 - 1) = 2147483647 abs(2147483648 - 2147483648) = 0 abs(2147483648 - 4294967294) = 2147483646 abs(2147483648 - 4294967295) = 2147483647 abs(4294967294 - 0) = 4294967294 abs(4294967294 - 1) = 4294967293 abs(4294967294 - 2147483648) = 2147483646 abs(4294967294 - 4294967294) = 0 abs(4294967294 - 4294967295) = 1 abs(4294967295 - 0) = 4294967295 abs(4294967295 - 1) = 4294967294 abs(4294967295 - 2147483648) = 2147483647 abs(4294967295 - 4294967294) = 1 abs(4294967295 - 4294967295) = 0