如何事先确定无符号计算是否可能溢出？

Question

作为我的个人项目，我正在实现一个任意精度数字类型，用于我的宠物项目。

我已经了解到所有流行、经过测试和稳健的库，我想作为自我提高教育项目而进行解决方案的研究。

我正在研究这个领域，并试图找出是否有某种方法可以在实际进行计算之前“大致”预测操作是否会导致溢出。我不太关心误判。

我希望能够使用适当的最小空间进行计算。如果计算结果仍在其本机范围内，我将保持在该范围内。

例如：如果每个64位整数足够大，则将两个64位整数相乘将导致溢出。我想检测到这一点，并仅在结果“可能”超过64位分辨率时将数字升级为我的数字类型。在此实验中，我将使用“有符号”数字。

最合理、高效的检测溢出/下溢的方法是什么？

- user177800

---

以前从未尝试过类似的项目，所以只有问题：提前了解溢出的意义是什么？优化小数字以快速处理，还是其他不太明显的原因？您需要一个精确的解决方案，还是接受可能会产生错误溢出警报的解决方案？ - vmatyi

你的问题和你对其中一个答案的评论表明你正在使用带符号的操作数，但标题说是无符号的。 到底是哪个呢？ 无符号算术可能更容易处理，并且可能更适合处理任意精度数字。 - Keith Thompson

我将使用无符号基本类型作为基本组件执行有符号任意计算，例如使用表示基数的无符号64位长整型数组。 - user177800

Answer 1

只取两个数中的最高位，向左移一位，如果这些数字的结果（例如：乘法）会导致溢出，则你有很大的可能性会发生溢出。

虽然它不是精确的，但速度非常快，并且是需要一个更大的数据类型来存储结果的好指示器。

这可能只对运算符代价昂贵的大型数据类型有意义，对于简单的事情（即使是64位数字），我认为您可以依赖CPU的内置算术...请参见此问题：超过64位时未定义的行为

- Karoly Horvath

---

因为这可能会导致溢出。如果确实发生了这种情况，那就意味着你的某个数字已经很大了。 - Xavier Ho

Answer 2

这方面有John Regehr的论文。

- Dan Kruchinin

Answer 3

通常情况下，使用朴素计算方法并检测是否发生溢出会更容易（而且通常更快）。您是否有特定的原因希望在进行计算之前检测可能性呢？

一旦计算完成，通常很容易检测是否发生了溢出。由于朴素操作成本低廉，即使发生了溢出，这也不会给您的计算增加太多成本，即使您最终需要重新做一些工作（通常情况下，您甚至都不需要这样做）。

以下是一个（非常）简单的例子：如果我将两个无符号64位数字相加，我可以通过将总和与任一加数进行比较来检查是否发生了溢出--如果总和小于任一加数，则发生了溢出。因此，在计算后检测溢出仅需要进行一次比较（非常便宜）。

- Stephen Canon

---

你的例子只适用于无符号操作数的情况，它在一般情况下不成立。 - Oliver Charlesworth

有符号溢出的行为是未定义的。 - Keith Thompson

@Keith：当然是针对原始类型。OP正在讨论实现任意精度类型。他需要能够处理溢出以增加表示（从而防止溢出！）。 - Oliver Charlesworth

@OliCharlesworth：我认为他在询问实现中使用的原始类型的溢出情况。例如，如果一个64位数字数组表示一个6400位数字，我认为他在询问64位溢出。Jarrod，你能澄清一下吗？ - Keith Thompson

一旦考虑到下溢，这种方法就不再适用了。 =| - Xavier Ho

@OliCharlesworth：需要注意两点：首先，在使用任意精度数字时，通常会将无符号大小和符号分别存储。因此，您通常只需要能够检测无符号溢出。其次，更重要的是，处理器检测有符号溢出/下溢与检测无符号溢出一样容易。没有一个整洁的可移植方式来获取设置的标志，但在任何合理的平台上都可以做到这一点--这是正确的方法来处理这个任务。 - Stephen Canon