实现数学公式时出现溢出问题

Question

我听说,当计算平均值时,start +(end-start)/ 2与(start + end)/ 2不同,因为后者会导致溢出.我不太明白为什么第二个会导致溢出而第一个不会导致溢出.实现可避免溢出的数学公式的通用规则是什么？

Answer 1

假设您使用的计算机的最大整数值为10,并且您希望计算平均值5和7.

第一种方法(开始+(结束开始)/ 2)给出

5 + (7-5)/2 == 5 + 2/2 == 6

第二种方法(开始+结束)/ 2给出溢出,因为中间12值超过了我们接受的"10"的最大值并且"包裹"到其他东西(如果你使用无符号数字,它通常会回绕到零,但如果你的号码签名,你可以得到一个负数!).

12/2 => overflow occurs => 2/2 == 1

当然,在实际的计算机中,整数溢出的值很大,比如2 ^ 32而不是10,但这个想法是一样的.不幸的是,没有"通用"方法可以摆脱我所知道的溢出,这在很大程度上取决于您使用的是哪种特定算法.然后事件变得更加复杂.根据您使用的数字类型,您可以获得不同的行为,除了上下溢之外还有其他类型的数值错误需要担心.

Answer 2

您的两个公式都会溢出，但是在不同的情况下：

• 在(start+end)您的部分(start+end)/2式会溢出时start和end均靠近整数限制在该范围的相同侧（即正或负二者）。
• 当正数和负数，并且两个值都接近可表示整数值的两端时(end-start)，start+(end-start)/2公式的部分将溢出。startend

没有“通用”规则，需要按情况进行：查看公式的各个部分，考虑可能导致溢出的情况，并提出避免这种情况的方法。例如，start+(end-start)/2当对具有相同符号的值求平均值时，可以显示该公式以避免溢出。

这是很难的方法。最简单的方法是将更高容量的表示形式用于中间结果。例如，如果您使用long long而不是int进行中间计算，并且int仅在完成后才将结果复制回去，则假设最终结果适合时，您将避免溢出int。