由于添加而发生溢出？

Question

您好，很抱歉这个 post 的蹩脚标题，只是找不到更好的标题。

所以，我正在解决名为 NumberOfDiscIntersections 的 Codility 练习。该解决方案需要一些基本的排序和一些次要的算术运算。我已经取得了 93% 的成绩，只有一个测试失败了。他们提供的描述如下：

For example, for the input [1, 2147483647, 0] the solution returned a wrong answer (got -1 expected 2).

问题可见here.

这是我的解决方案：

typedef long long int my_type; //can't use unsigned!
#define LIMIT 10000000

//method used by qsort()
int comp(const void* left, const void* right) {
    my_type arg1 = *(const my_type*)left;
    my_type arg2 = *(const my_type*)right;

    if(arg1 < arg2) return -1;
    if(arg2 < arg1) return 1;
    return 0;
}

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)

    //allocate two arrays to hold beginning and ending points of each circle 
    my_type *lower = calloc(N, sizeof(my_type));
    my_type *upper = calloc(N, sizeof(my_type));
    int i;
    my_type count = 0;

    //initialize arrays
    for(i = 0; i < N; i++) {
        lower[i] = i - A[i];
        upper[i] = i + A[i];
    }

    qsort(lower, N, sizeof(my_type), comp);
    qsort(upper, N, sizeof(my_type), comp);

    int open = 0;
    int upper_index = 0;

    for(i = 0; i < N; i++) {
        while(lower[i] > upper[upper_index]) {
            //printf("closing %d\n", upper[upper_index]);
            upper_index++;
            open--;
        }

        open++;
        count += (open-1);

        //printf("opening %d\n", lower[i]);
    }

    free(lower);
    free(upper);

    return ((int)count <= LIMIT) ? (int)count : -1;
}

Answer 1

这些的右边

lower[i] = i - A[i];
upper[i] = i + A[i];

执行int加法。您必须投射其中一个操作数：

lower[i] = (my_type)i - A[i];
upper[i] = (my_type)i + A[i];

防止整数溢出。

由于添加而发生溢出？

Overflow happening because of addition?

c

math

integer-arithmetic