计算溢出中的整数绝对差值
我想计算两个整数的绝对差值。 天真地说，这只是abs(a - b) 。 但是，这有几个问题，取决于整数是有符号的还是无符号的：
对于无符号整数，如果b大于a ，那么b a - b将是一个很大的正数，而绝对值操作不会解决这个问题。
对于有符号整数， a - b可能超出可以表示为有符号整数的值范围之外，从而导致未定义的行为。 （显然，这意味着结果将需要是一个无符号整数。）
如何以有效的方式解决这些问题？
我想要一个算法（或算法对），它既适用于有符号整数也适用于无符号整数，并且不依赖将值转换为更大的整数大小。
（另外，为了澄清：我的问题不是如何在代码中编写它，而是为了保证溢出安全，我应该写些什么。将abs(a - b)计算为有符号值，然后转换为无符号值不起作用，因为有符号整数溢出通常是未定义的操作，至少在C中）
（在问这个问题后，我一直在努力解决这个问题 - 我认为这会更困难，如果有更好的问题，我仍然会欢迎其他答案！）
无符号整数的解决方案相对比较简单（如Jack Toole的回答所述），并且通过在减法之外移动（隐含的）条件来工作，以便我们总是从较大的数字中减去较小的数字，包装值为零：
if (a > b)
return a - b;
else
return b - a;
这就留下了有符号整数的问题。 考虑以下变化：
if (a > b)
return (unsigned) a - (unsigned) b;
else
return (unsigned) b - (unsigned) a;
我们可以很容易地证明这是通过使用模运算来实现的。 我们知道a和(unsigned) a是一致的模UINT_MAX 。 此外，无符号整数减法操作与实际减法模UINT_MAX ，所以结合这些事实，我们知道(unsigned) a - (unsigned) b与a - b模UINT_MAX的实际值UINT_MAX 。 最后，因为我们知道a - b的实际值必须介于0和UINT_MAX-1 ，所以我们知道这是一个精确的等式。
这里有一个想法：如果我们没有签名，我们只是采取正确的区别。 如果我们签了名，我们返回相应的无符号类型：
#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);
}
用法： int a, b; unsigned int d = absdiff(a, b); int a, b; unsigned int d = absdiff(a, b);
码：
#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;
}
输出：
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