c ++: int переполняется, когда он меньше INT_MAX

Question

Я написал код, подобный приведенному ниже.

#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;

long long int N, K;



int main() {
    cin >> N >> K;

    long long int result = 0;
    int IntResult = 0;

    for (long long int i = K; i <= N + 1; i++) {
        result += 1 + (N + 1 - i) * i;
        IntResult += 1 + (N + 1 - i) * i;
    }

    cout << result % (1000000000 + 7) << endl;
    cout << IntResult % (1000000000 + 7) << endl;
    return 0;
}

И когда я введу «141421 35623», этот код выдаст ниже.

141421 35623
220280457
619089693

Правильный ответ - «220280457». Результат int неверен.

Я поместил cout в a для l oop и проверил значение IntResult.

Затем я обнаружил, что IntResult стал отрицательным значением в a для l oop. Это переполнено!

Но почему? Максимальное значение int равно "2147483648". Это больше, чем «220280457».

И процесс для l oop - это всего лишь дополнение, поэтому я не могу понять, почему он переполнен.

Пожалуйста, помогите мне!

Answer 1

Вы переполнены на первой итерации.

1 + (N + 1 - i) * i

Меньше, чем

(N - i)*i

Первая итерация:

(141421-35623)*35623

К сожалению, переполнение, которое является UB в целые числа со знаком.

IntResult % (1000000000 + 7)

Бывает после и не имеет значения, так как IntResult содержит неизвестное значение.

Answer 2

В вашем l oop выражение 1 + (N + 1 - i) * i (которое оценивается как long long int) быстро и часто становится больше INT_MAX, и это вызывает переполнение целых чисел при попытке добавьте его к (int) result.

Добавление быстрой «проверки» в ваш код, как показано ниже, продемонстрирует это:

int main()
{
    cin >> N >> K;
    long long int result = 0;
    int IntResult = 0;
    int count = 0;
    for (long long int i = K; i <= N + 1; i++) {
        // Check for intermediate overflow potential...
        long long int lli = 1LL + (N + 1LL - i) * i;
        if (lli > INT_MAX) cout << lli << " (" << ++count << ")"  << endl;
        result += 1 + (N + 1 - i) * i;
        IntResult += 1 + (N + 1 - i) * i;
    }
    cout << result % (1000000000 + 7) << endl;
    cout << IntResult % (1000000000 + 7) << endl;
    return 0;
}

Когда я запускаю это Код на моей платформе (32-битный int и 64-битный long long int) с вашими заданными входами (141421 и 35623), строка "проверка переполнения" фактически происходит 88,498 раз ! Вот последние три строки вывода:

...
2147524241 (88498)
220280457
619089693

Более того, даже если проверенное выше дополнение не может само по себе переполнить int, результат добавления его к существующему (потенциально не -зеро) значение в result все еще может сделать это. Действительно, изменение строки 'check' на это:

if ((lli + result) > INT_MAX) cout << lli << " (" << ++count << ")"  << endl;

показывает, что l oop переполняется на на каждой итерации!