12

可能重复：
在 C/C++ 中检测整数溢出的最佳方法

我在一次采访中被问到这个问题：“将数字的字符串表示形式转换为整数”。但是如果这个数字超过了可以存储在一个 32 位整数中的最大值，它必须抛出一个错误。我的问题是我们如何检查一个数字是否溢出 32 位 unsigned int ？

4

3 回答 3

11

在循环中，您获得了由前几位确定的整数的当前值。你将要做：

curval = curval * 10 + digit;  // digit converted from '0'..'9' to 0..9 already

您可以使用以下方法测试溢出：

if (curval > UINT32_MAX / 10 || (curval == UINT32_MAX / 10 && digit > UINT32_MAX % 10))
    ...overflow would occur...
else
    curval = curval * 10 + digit; // overflow did not occur

除法和取模操作是编译时操作，而不是运行时操作。

与使用“大于 32 位无符号整数进行计算”相比，这种方法的一个优点是，它可以uintmax_t通过将常量从 UINT32_MAX 更改为 UINT64_MAX 或 UINTMAX_MAX 来扩展以使用更大的整数（64 位整数和整数） . 这就是所有必要的（当然，除了更改变量类型）。

相同的基本测试也适用于有符号类型，但有一个额外的复杂性。出于演示目的使用 16 位整数更容易（输入和思考的数字更少），所以我切换到 16 位二进制补码short：

  • USHRT_MAX= 65535
  • SHRT_MAX= 32767
  • SHRT_MIN= -32768

问题是该short类型可以存储 -32768 但您可以累积的最大正值是 32767。对于除 SHRT_MIN 之外的所有值，上面的测试都可以正常工作。有办法解决这个困境。一种是curval在计算过程中将 存储为负值，如果它应该是正值，则在返回之前将其取反。那么你的测试可能是：

if (curval < SHRT_MIN / 10 || (curval == SHRT_MIN / 10 && digit > -(SHRT_MIN / 10))
    ...overflow would occur...
else
    curval = curval * 10 - digit; // Note subtraction!

在否定负值之前，您仍然必须检查curval不是。SHRT_MIN（理论上，您应该检查-SHRT_MAX != SHRT_MIN以允许除二进制补码以外的其他系统；我引用的限制值满足该条件。）

当然，同样的想法和技巧也适用于INT_MAX、和。INT32_MAXINT64_MAXINTMAX_MAX

于 2012-12-01T17:12:58.973 回答
7

（我查看了这个问题的可能重复项，我不确定阅读内容会有多大用处，因为在面试环境中，您应该描述一般的想法/方法）

回答面试问题的一部分是提出澄清问题（面试官期望你提供的重要清单项目之一）。

因此，您的调查范围至少应包括以下内容：

  • 你可以使用unsigned long long/ uint64_t（64 位 int）吗？
  • 字符串从哪里来？stdin/ 从文件中读取 / 硬编码为字符串文字？
  • 它是否以十进制表示形式提供给您？二进制/八进制/十六进制？
  • 应该抛出什么样的错误？我们是否尝试恢复并继续执行？故障安全默认值是多少？

假设您的面试官告诉您它是十进制表示+您可以使用unsigned long long：

  • 首先检查位数： 32 位unsigned int范围在0 to 4,294,967,295. 如果数字的十进制字符串表示超过 10 个字符（超过 10 位），则它已经溢出；引发错误。
  • 接下来，将数字保存到 anunsigned long long并除以UINT32_MAX+1=4294967296。如果结果大于0，则溢出；引发错误。
于 2012-12-01T16:56:19.803 回答
0

使用uint64_t. 您将一次添加一个数字；对于每个数字，您将乘以 10 并添加下一个字符的值。处理完每个字符后，查看结果是否大于UINT32_MAX; 如果是，则以错误退出（或在溢出时应该执行的任何操作）。完成后，将数字作为uint32_t. uint64_t,uint32_t并UINT32_MAX在 中定义stdint.h。

于 2012-12-01T17:02:27.583 回答