我想计算两个整数的绝对差。天真地,这只是 abs(a - b)
。然而,这有几个问题,具体取决于整数是有符号的还是无符号的:
对于无符号整数,如果
b
大于a
,则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
的实际值。最后,因为我们知道 a - b
的实际值必须在 0
和 UINT_MAX-1
之间,所以我们知道这是一个精确的平等。
关于algorithm - 以溢出安全的方式计算整数绝对差?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8024480/