Computing integer absolute differences in overflow-safe ways?

Question

I would like to compute the absolute difference of two integers. Naively, this is just abs(a - b). However, this has a couple of problems, depending on whether the integers are signed or unsigned:

• For unsigned integers, a - b will be a large positive number if b is larger than a, and the absolute value operation will not fix that.

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

How can these problems be addressed in an efficient way?

I would like an algorithm (or pair of algorithms) that works for both signed and unsigned integers, and does not rely on casting the values to a larger integer size.

(Also, to clarify: my question is not how to write this in code, but what exactly I should be writing in order to guarantee overflow-safety. Computing abs(a - b) as a signed value and then casting to an unsigned value doesn't work, because signed integer overflow is typically an undefined operation, at least in C.)

Answer 1

(I've been working this out on my own after asking the question -- I thought it would be harder, and I'd still welcome other answers if there are better ones!)

The solution for unsigned integers is relatively straightforward (as described in Jack Toole's answer), and works by moving the (implied) conditional outside the subtraction so that we are always subtracting the smaller number from the larger one, and are not comparing a potentially-wrapped value to zero:

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

This just leaves the question of signed 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 by using modulo arithmetic. We know that a and (unsigned) a are congruent modulo UINT_MAX. Further, the unsigned-integer subtraction operation is congruent to actual subtraction modulo UINT_MAX, so combining these facts, we know that (unsigned) a - (unsigned) b is congruent to the actual value of a - b modulo UINT_MAX. Finally, because 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

Here's an idea: if we're unsigned, we just take the correct difference. If we're signed, 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);