Как проверить, длинный ли A + B? (оба A и B длинны)

У меня есть 2 числа: A и B. Мне нужно вычислить A+B где-то в моем коде. И A, и B являются long long и могут быть положительными или отрицательными.

Мой код работает неправильно, и я подозреваю, что проблема возникает при вычислении A+B. Я просто хочу проверить, превышает ли A+B диапазон long long. Таким образом, любой метод является приемлемым, поскольку я использую его только для отладки.

Ответ 1

Переполнение возможно только тогда, когда оба числа имеют один и тот же знак. Если оба положительные, то вы имеете переполнение, если математически A + B > LLONG_MAX, или эквивалентно B > LLONG_MAX - A. Так как правая часть неотрицательна, последнее условие уже подразумевает B > 0. Аналогичный аргумент показывает, что для отрицательного случая нам также не нужно проверять знак B (благодаря Ben Voigt, указав, что проверка знака на B не требуется). Затем вы можете проверить

if (A > 0) {
    return B > (LLONG_MAX - A);
}
if (A < 0) {
    return B < (LLONG_MIN - A);
}
return false;

для обнаружения переполнения. Эти вычисления не могут переполняться из-за начальных проверок.

Проверка знака результата A + B будет работать с гарантированной семантикой обтекания переполняющих целочисленных вычислений. Но переполнение целых чисел со знаком - это поведение undefined, и даже на процессорах, где оболочка является реализованным поведением, компилятор может предположить, что поведение undefined не происходит и полностью удаляет проверку переполнения при его реализации. Таким образом, проверка, предложенная в комментариях к вопросу, крайне ненадежна.

Ответ 2

Что-то вроде следующего:

long long max = std::numeric_limits<long long>::max();
long long min = std::numeric_limits<long long>::min();

if(A < 0 && B < 0) 
    return B < min - A;
if(A > 0 && B > 0)
    return B > max - A;

return false;

Мы можем рассуждать об этом следующим образом:

Если A и B являются противоположными знаками, они не могут переполняться - то, что больше нуля, должно быть больше, чем max, или единица меньше нуля должна быть меньше min.
В остальных случаях достаточно простой алгебры. A + B > max => B > max - A будет переполняться, если они оба положительные. В противном случае, если они оба отрицательные, A + B < min => B < min - A.

Ответ 3

Кроме того, если вы используете его только для отладки, вы можете использовать следующий "взломать", чтобы прочитать бит переполнения от последней операции напрямую (при условии, что ваш компилятор /cpu поддерживает это):

int flags;
_asm {
    pushf       // push flag register on the stack
    pop flags   // read the value from the stack
}
if (flags & 0x0800) // bit 11 - overflow
    ...

Ответ 4

Маскируйте знаки, отбрасывайте значения без знака и выполняйте добавление. Если он выше 1 << (sizeof(int) * 8 - 1), то у вас есть переполнение.

int x, y;
if (sign(x) == sign(y)){
    unsigned int ux = abs(x), uy = abs(y);    
    overflow = ux + uy >= (1 << (sizeof(int) * 8 - 1));
}

Еще лучше, напишите шаблон:

template <typename T> 
bool overflow(signed T x, signed T y){
    unsigned T ux = x, uy = y;
    return ( sign(x) == sign(y) && (ux + uy >= (1 << (sizeof(T) * 8 - 1)));
}