algorithm - 以溢出安全的方式计算整数绝对差？

Question

我想计算两个整数的绝对差。天真地，这只是 abs(a - b)。然而，这有几个问题，具体取决于整数是有符号的还是无符号的:

• 对于无符号整数，如果 b 大于 a，则 a - b 将是一个大的正数，并且绝对值操作不会解决这个问题。

• 对于有符号整数，a - b 可能超出可以表示为有符号整数的值范围，从而导致未定义的行为。 (显然，这意味着结果需要是无符号整数。)

如何有效地解决这些问题？

我想要一种算法(或算法对)适用于有符号和无符号整数，并且不依赖于将值转换为更大的整数大小。

(另外，澄清一下:我的问题不是如何在代码中编写它，而是为了保证溢出安全我应该写什么。计算 abs(a - b) 为有符号值然后转换为无符号值是行不通的，因为有符号整数溢出通常是未定义的操作，至少在 C 中是这样。)

Answer 1

(我在问完这个问题后一直在自己解决这个问题——我认为这会更难，如果有更好的答案，我仍然欢迎其他答案!)

无符号整数的解决方案相对简单(如 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 的实际值。最后，因为我们知道 a - b 的实际值必须在 0 和 UINT_MAX-1 之间，所以我们知道这是一个精确的平等。