如何在不溢出 int 的情况下检查 INT_MAX

Question

我创建了一个 BigInt class，它通过将每个数字存储在一个向量中来允许远远超过整数最大值的巨大数字（从任何基数 2-36）。我需要能够将其转换回整数，但如果达到最大值，则 return int max/min，否则会出现整数溢出。

我的问题是如何在不溢出我正在构建的整数的情况下检查我是否超过了最大值。我已经尝试将底部的 if 语句移动到 for 循环中，但我的整数仍然溢出。我觉得解决方案很简单，但我就是无法掌握它。

//  Convert BigInt to integer base 10 and return that int
//    If BigInt > INT_MAX, return INT_MAX.
//    If BigInt < INT_MIN, return INT_MIN.
int BigInt::to_int() const{
   int number = 0;
   for(size_t i = 0; i < vec.size(); i++) {
       number += vec[i] * pow(base, i);
   }

   if (!isPositive) { number *= -1; }
   if (number > INT_MAX) { return INT_MAX; }
   if (number < INT_MIN) { return INT_MIN; }

   return number;
}

Answer 1

将 int 值与 INT_MAX 进行比较是没有意义的，除非相等，因为所有值都小于或等于。

在溢出的有符号操作之后执行溢出检查是没有意义的，因为它们要么表明没有溢出，要么程序的行为未定义。始终在尝试会导致结果溢出的操作之前进行检查。

在这种情况下，将 INT_MAX 转换为您的 BigInt 类型并将其与 *this 进行比较。

Answer 2

初步信息：你需要在计算溢出的东西之前检查溢出。如果溢出已经发生，那就太晚了。

向您的 to_int() 版本添加溢出检查很棘手，因为您从一个地方开始建立您的价值。由于这种方法，您尝试添加 pow(base, i)，它本身可能会溢出 int，而且事先不容易检测到。可能，但让我们考虑其他事情。

如果你要在一个地方建立你的值 ending（即重复计算 number*base + digit），你可以在相乘之前检查溢出。这是一些数学，使用较短的名称以便于阅读。设 x 和 M 为整数，base 为正整数，d 为小于 base 的非负整数。（M 是“max”的缩写，d 是“digit”的缩写。）除法将表示实值除法，因为我可以 trunc() 结果得到整数除法。我们想知道 x*base + d 与 M 相比如何。

如果 x*base + d <= M 然后除以 base 得到 x + d/base <= M/base，因此 x <= trunc(M/base).
反之，如果 x > trunc(M/base) 那么 x*base + d > M.

如果 x*base + d >= M 然后除以 base 得到 x + d/base >= M/base，因此 x >= trunc(M/base).
反之，如果 x < trunc(M/base) 那么 x*base + d < M.

如果x == trunc(M/base)那么x*base == trunc(M/base)*base。两边加上M%base得到x*base + M%base == M。好吧，我希望你能接受 trunc(M/base)*base + M%base == M 的观察。如果你能接受那么多，那么x*base + d和M的比较就和d和M%base的比较一样了。

算完了。让我们把它写成代码。您可能还会注意到性能提升，具体取决于编译器的优化方式。

// Tests if number * base + next_digit will overflow an int. bool will_overflow(int number, int base, int next_digit ) { if ( number > INT_MAX/base ) return true; if ( number < INT_MAX/base ) return false; // It's close enough that the next digit decides it. return next_digit > INT_MAX % base; }

// Convert BigInt to integer base 10 and return that int // If BigInt > INT_MAX, return INT_MAX. // If BigInt < INT_MIN, return INT_MIN. int BigInt::to_int() const { int number = 0; // Loop in the reverse direction. Be careful with unsigned values! for(size_t i = vec.size(); i > 0; --i) { if ( will_overflow(number, base, vec[i-1]) ) return isPositive ? INT_MAX : INT_MIN; number = number * base + vec[i-1]; } return number; }

我会指出一个小作弊。有一个负值适合 int，但其绝对值大于 INT_MAX。如果出现该奇异值，此函数将错误地将其检测为溢出和 return INT_MIN。幸运的是，这很好，因为奇异值是 INT_MIN。 :)

如何在不溢出 int 的情况下检查 INT_MAX

How to check for INT_MAX without overflowing int

c++

vector

overflow