问题标签 [integer-overflow]

所以我最近一直在研究米勒-拉宾素数测试的实现。我将它限制在所有 32 位数字的范围内，因为这是一个有趣的项目，我正在做它来熟悉 c++，并且我不想使用任何 64 位一会儿。一个额外的好处是该算法对所有 32 位数字都是确定性的，因此我可以显着提高效率，因为我确切地知道要测试哪些证人。

因此，对于低数字，该算法运行得非常好。但是，该过程的一部分依赖于模幂运算，即 (num ^ pow) % mod。所以，例如，

这是我一直用于此模幂运算的代码：

正如您可能已经猜到的那样，当参数都是非常大的数字时，就会出现问题。例如，如果我想测试数字 673109 的素数，我必须在某一时刻找到：

(2 ^ 168277) % 673109

现在 2 ^ 168277 是一个非常大的数字，并且在过程中的某个地方它会溢出测试，从而导致不正确的评估。

在反面，论点如

4000111222 ^ 3 % 1608

出于同样的原因，也评估不正确。

有没有人对模幂运算提出建议，以防止这种溢出和/或操纵它以产生正确的结果？（在我看来，溢出只是模的另一种形式，即 num % (UINT_MAX+1)）

首先，让我说我理解我所描述的问题如何以及为什么会发生。我是计算机科学专业的，我了解上溢/下溢和有符号/无符号算术。（对于不熟悉该主题的人，Apple 的安全编码指南简要讨论了整数溢出。）

我的问题是关于在检测到此类错误后报告并从中恢复，尤其是在 Objective-C 框架的情况下。（我编写和维护CHDataStructures。）我有一些集合类，它们为存储对象分配内存并根据需要动态扩展。我还没有看到任何与溢出相关的崩溃，可能是因为我的测试用例大多使用健全的数据。但是，考虑到未经验证的值，事情可能会很快爆发，我想防止这种情况发生。

我已经确定了至少两种可能发生这种情况的常见情况：

1. 调用者将一个非常大的无符号值（或负符号值）传递给-initWithCapacity:.
2. 添加了足够多的对象导致容量动态扩展，并且容量已经增长到足以导致溢出。

简单的部分是检测是否会发生溢出。（例如，在尝试分配length * sizeof(void*)字节之前，我可以检查是否length <= UINT_MAX / sizeof(void*)，因为未通过此测试将意味着产品将溢出并可能分配比预期小得多的内存区域。在支持它的平台上，checkint.h API是另一种选择。）更难的部分是确定如何优雅地处理它。在第一种情况下，调用者可能更有能力（或至少在心态上）来处理失败。第二种情况可能发生在将对象添加到集合的代码中的任何位置，这可能是非常不确定的。

那么，我的问题是：在这种情况下发生整数溢出时，“好公民”Objective-C 代码应该如何行动？（理想情况下，由于我的项目是一个与 Cocoa 中的 Foundation 精神相同的框架，我想模拟它的行为方式以实现最大的“阻抗匹配”。我发现的 Apple 文档在关于这一切。）我认为无论如何，报告错误是给定的。由于添加对象的 API（这可能导致场景 2）不接受错误参数，如果有的话，我真的可以做些什么来帮助解决问题？在这种情况下，什么才是真正可以接受的？如果我能做得更好，我不愿意故意编写容易崩溃的代码......

Trying to do front-end validation on an HTML input instead of throwing an exception in the Java back-end.

我在使用 C++ 时遇到了一个奇怪的问题，其中长数据类型早就溢出了。我正在做的（到目前为止取得了成功）是让整数表现得像浮点数，以便将范围 [-32767,32767] 映射到 [-1.0,1.0]。它绊倒的地方是更大的参数表示大于 1.0 的浮点数：

我得到的输出是：

所以 times(98301,32767) 类似于 3.0*1.0。当时间的参数小于 32767 (1.0) 时，此代码可以完美运行，但带有上述参数的任何中间步骤都不应溢出 64 位 long。

有任何想法吗？

有没有一种通用的方法来检查给定数据类型（uint32、int 等）的上溢或下溢？

我正在做这样的事情：

当我在一些迭代后打印 a 时，它会显示一个大数字，例如：4294963846。

微软已经在 GetTickCount 的文档中说过，你永远不能比较滴答计数来检查是否已经过了一个间隔。例如：

不正确（伪代码）：

上面的代码很糟糕，因为它很容易发生刻度计数器的翻转。例如，假设时钟接近其范围的末端：

然后你执行你的检查：

立即满足，因为GetTickCount 大于endTime：

解决方案

相反，您应该始终减去两个时间间隔：

看同样的数学：

在 C/C++ 中，这一切都很好，编译器以某种方式运行。

但是德尔福呢？

但是当我在 Delphi 中执行相同的数学运算时，在 ( {Q+}, ) 上进行溢出检查时，两个滴答计数的减法会在TickCount翻转{$OVERFLOWCHECKS ON}时生成 EIntOverflow 异常：

这个问题的预期解决方案是什么？

编辑：我试图暂时关闭OVERFLOWCHECKS：

但是减法仍然会引发EIntOverflow异常。

有没有更好的解决方案，涉及强制转换和更大的中间变量类型？

更新

我问的另一个 SO 问题解释了为什么{$OVERFLOWCHECKS}不起作用。它显然只适用于功能级别，而不是行级别。因此，虽然以下内容不起作用：

以下确实有效：

我有一些导致下溢的代码：

减法本身确实会产生溢出（下溢），但我不希望 Delphi 抛出EIntOverflow异常。所以我尝试通过禁用溢出检查来禁用溢出检查代码的生成：

然而，即使有这个OVERFLOWCHECKS OFF选项，它仍然会引发异常。并且生成的代码仍然包含检查：

关于以下文档的提醒$Q：

溢出检查

类型开关
语法{$Q+} 或 {$Q-}
{$OVERFLOWCHECKS ON} 或 {$OVERFLOWCHECKS OFF}
默认{$Q-}
{$OVERFLOWCHECKS OFF}
范围本地

评论

$Q 指令控制溢出检查代码的生成。在 {$Q+} 状态下，检查某些整数算术运算（+、-、*、Abs、Sqr、Succ、Pred、Inc和Dec）是否溢出。每个整数算术运算的代码后面都有附加代码，用于验证结果是否在支持的范围内。如果溢出检查失败，则会引发 EIntOverflow 异常（如果未启用异常处理，则程序终止）。

$Q 开关通常与 $R 开关一起使用，它启用和禁用范围检查代码的生成。启用溢出检查会减慢您的程序并使其变得更大，因此仅使用 {$Q+} 进行调试。

如何使用$OVERFLOWCHECKS OFF禁用溢出检查代码的生成？

梅森的回答奏效了。修改后的代码是：

对于谷歌爬虫，替代问题措辞：如何在 Delphi 中暂时禁用溢出检查？

我正在为 MATLAB/Octave 中的一些 VHDL 代码开发验证工具。因此我需要产生“真实”溢出的数据类型：

稍后，如果我可以定义变量的位宽会很有帮助，但现在这并不重要。

当我构建一个类似 C 的示例时，变量会增加直到小于零，它会永远旋转：

我尝试的另一种方法是自定义“溢出”例程，每次更改数字后都会调用该例程。这种方法非常缓慢，不切实际，而且根本不适用于所有情况。有什么建议么？

我试图找到一组数据的线性趋势线。该集合包含成对的日期（x 值）和分数（y 值）。我正在使用此代码的一个版本作为我的算法的基础。

我得到的结果相差了几个数量级。我假设舍入错误或溢出存在一些问题，因为我使用的是 Date 的 getTime 方法，它会给你大量的毫秒数。有人对如何最小化错误并计算正确结果有建议吗？

我正在实现一个数据库应用程序，我将同时使用 JavaDB 和 MySQL 作为数据库。我的表中有一个 ID 列，其类型为整数，我使用数据库 auto_increment-function 作为值。

但是当我收到超过 2（或 4）十亿个帖子并且整数还不够时会发生什么？整数是否溢出并继续，还是抛出了我可以处理的异常？

是的，我可以更改为 long as 数据类型，但是如何检查何时需要？如果我使用 long 作为 ID 列的数据类型，我认为获取 last_inserted_id() 函数会出现问题。