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

Question

我想计算两个整数的绝对差值.天真,这只是abs(a - b).但是,这有两个问题,具体取决于整数是有符号还是无符号:

• 对于无符号整数,a - b如果b大于,则将是一个大的正数a,并且绝对值操作将无法解决该问题.

• 对于有符号整数,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,我们知道这是完全相等的.