c++ - INT_MAX+a-b 不会导致溢出但 INT_MAX*a/b 会导致溢出(如果 a>1 且 a=b)吗？

Question

我想解决一些关于溢出的问题。我有一些数据使用int来存储，数据不会导致溢出但计算中间可能会导致溢出。

比如我需要存储正方形的对角线，边长是50000，所以对角线是70710，边和对角线都远小于INT_MAX，但是为了计算，aa+b b in sqrt(aa+bb) 会导致溢出。

我想遵循“只使用 int”规则，所以我可能需要每次都转换每个变量:

int f=(long)a+(long)b*(long)c/(long)d-(long)e;

但是每次add(long)都会影响可读性，我测试一下哪些操作可能会溢出，哪些操作可能会自动转换:

#include <sstream>
int main(){
    int a=rand();
    int b=a;
    printf("%d\n",a);
    printf("%d\n",INT_MAX);
    printf("\n");
    printf("%d\n",INT_MAX+a-b);
    printf("%d\n",INT_MAX-b+a);
    printf("%d\n",a+INT_MAX-b);
    printf("%d\n",a-b+INT_MAX);
    printf("%d\n",-b+a+INT_MAX);
    printf("%d\n",-b+INT_MAX+a);
    printf("\n");
    printf("%d\n",INT_MAX*a/b);
    printf("%d\n",INT_MAX/b*a);
    printf("%d\n",a*INT_MAX/b);
    printf("%d\n",a/b*INT_MAX);
    printf("\n");
    printf("%ld\n",(long)INT_MAX*a/b);
    printf("%ld\n",INT_MAX*a/(long)b);
    return 0;
}

输出是:

16807
2147483647

2147483647
2147483647
2147483647
2147483647
2147483647
2147483647

127772
2147480811
127772
2147483647

2147483647
127772

我使用 rand() 来确保没有编译时间计算，我发现对于 + 和 - 对于不同的 INT_MAX、+a 和 -b 序列结果是相同的，但对于 *a 和/b 则不同。

我还发现甚至使用转换，(long)INT_MAXa/b 是正常的，但 INT_MAXa/(long)b 不是。

我猜想对于+和-，如果结果小于INT_MAX，即使计算中间(例如:INT_MAX+a-b中的INT_MAX+a)也可能导致溢出，但对于*和/，溢出中间会影响结果，对吗？

同样对于*和/，我猜操作从左手边开始，所以类型转换需要从左手边开始(例如:(long)INT_MAX*a/b)，是不是也对？

所以，如果我的数据不会导致溢出但是计算可能会导致溢出，是

int f=a+b*c/d-e;

只需改写为

int f=a+(long)b*c/d-e;

?

Answer 1

data does not cause overflow but the calculation intermediate may cause overflow.

要避免 int 溢出，这是未定义的行为，最简单的解决方案是使用足够宽的整数类型。

int foo1(int a, int b, int c, int d) {
  int f=(long)a+(long)b*(long)c/(long)d-(long)e; // OP's stating point, but see foo2
  return f;
}

but each time add (long) affects readability

为避免不必要的转换及其可读性，请仅在需要时使用 * one。一个好的编译器会优化显式乘法，但保留类型提升。

int foo2(int a, int b, int c, int d) {
  int f = a + 1L*b*c/d - e; // Cleaner yet see foo3
  return f;
}

为确保潜在的更宽类型足够宽(long 可能与 int 的宽度相同)，执行编译时测试

// Find a type where INT_MAX*INT_MAX <= some_type_MAX
#if LONG_MAX/INT_MAX >= INT_MAX
  #define WIDE1 1L
#elif LLONG_MAX/INT_MAX >= INT_MAX
  #define WIDE1 1LL
#elif INTMAX_MAX/INT_MAX >= INT_MAX
  #define WIDE1 ((intmax_t)1)
#else
  #error Out of luck
#endif

int foo3(int a, int b, int c, int d) {
  int f = a + WIDE1*b*c/d - e;
  return f;
}

要避免仅使用 int 类型的数学是工作。

---

.. but for calculation, aa+bb in sqrt(aa+bb) will cause overflow.

对于这种情况

int hypoti1(int a, int b) {
  return sqrt(WIDE1*a*a + WIDE1*b*b);
}

// or simply

int hypoti1(int a, int b) {
  return hypot(a, b);
}