Computing integer absolute differences in overflow
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.)
(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.
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); int a, b; unsigned int d = absdiff(a, b);
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) = %un",
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) = %un",
testDataUnsigned[j],
testDataUnsigned[i],
AbsDiffUnsigned(testDataUnsigned[j], testDataUnsigned[i]));
return 0;
}
Output:
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
上一篇: 什么是最精确的数字分割方法？
下一篇: 计算溢出中的整数绝对差值