Почему x - y не переполняется для TMin в этой функции? Почему в этом случае функция неверна?

Я читал об этой функции:

int tadd_ok ( int x, int y ) {  
    int sum = x + y;  
    int negative_overflow = x < 0 && y < 0 && sum >= 0;   
    int positive_overflow = x >=0 && y >= 0 && sum < 0;  
    return !negative_overflow && !positive_overflow;
}

У этой функции есть проблема, когда мы передаем в качестве аргумента для y TMin (т.е. наименьшее дополнение 2).
В этом случае -y будет -y при передаче, т.е. все еще будет TMin первое условие покажет, что у нас есть отрицательный переполнение для значений x, которые являются отрицательными.
Затем я прочитал, что на самом деле "x - y не переполняется" в этих случаях.

Насколько я понимаю, проблема этой функции в том, что она не учитывает угловой случай передачи минимального отрицательного числа. Я вижу, что он вернет отрицательное_переполнение. Я не вижу/не понимаю, почему это неправильно.
Может ли кто-нибудь помочь мне понять это?


c types integer integer-overflow integer-arithmetic
person Cratylus    schedule 21.09.2014    source источник
comment
Проблема с этой функцией заключается в том, что она пытается обнаружить переполнение после того, как оно могло произойти. Это неправильно, так как в случае переполнения носовые демоны уже произошли бы.   -  person ouah    schedule 22.09.2014
comment
@ouah: Я предполагаю, что правильная функция пытается обнаружить до того, как это произойдет? Я не знаю, в чем разница между этими подходами. Помимо этого ошибочного подхода, почему считается, что TMin не переполняется?   -  person Cratylus    schedule 22.09.2014
comment
Проблема в том, что, как сказал ouah, компилятор C пытается вас обмануть вместо того, чтобы помочь. Вместо того, чтобы переполнять целые числа со знаком, используя арифметику с дополнением до 2, а затем позволять вам проверять результирующую сумму, многие компиляторы C предполагают, что oevrflow никогда не поможет, и оптимизируют вашу проверку переполнения. Для получения дополнительной информации см. этот вопрос   -  person hugomg    schedule 22.09.2014
comment
Да, обнаружение должно быть сделано раньше. Что касается INT_MIN, я не совсем понимаю ваш вопрос, поскольку вы никогда не вычисляете -y в tadd_ok.   -  person ouah    schedule 22.09.2014
comment
@ouah: проблема связана с тем, что функцию можно вызвать как: tadd_ok(x, -y);, чтобы проверить, не переполнится ли x - y. Проблема заключается в передаваемом аргументе, т.е. в том, как он называется   -  person Cratylus    schedule 22.09.2014
comment
@Cratylus, но это не имеет ничего общего с функцией tadd_ok, если вы делаете что-то вроде -INT_MIN (обратите внимание на -), вы уже вызываете неопределенное поведение, и внутри функции tadd_ok вы мало что можете сделать.   -  person ouah    schedule 22.09.2014
comment
@ouah: Но -INT_MIN - это -INT_MIN. Он зацикливается из-за асимметрии. По какой-то причине я думаю, что цель этого примера кода - показать, что INT_MIN на самом деле не может вызвать переполнение. Но я не понимаю, почему   -  person Cratylus    schedule 22.09.2014
comment
@Cratylus -INT_MIN не выполняет перенос, он вызывает неопределенное поведение. Переполнение целого числа со знаком вызывает неопределенное поведение.   -  person ouah    schedule 22.09.2014
comment
@ouah: Это специфично для C? Я имею в виду, что в теории CS он обертывается вокруг, верно? Поскольку диапазон равен [-2 ^ 31, 2 ^ 31-1], поэтому в положительных числах нет эквивалента -2 ^ 31, поэтому он переходит к еще одному, то есть к -2 ^ 31.   -  person Cratylus    schedule 22.09.2014
comment
Да, это специфично для C, и это заноза в заднице. Стандарт C появился в то время, когда не каждый компьютер использовал арифметику с дополнением до 2, поэтому переполнение со знаком считалось неопределенным поведением. К сожалению, это не означает неопределенное поведение. Многие компиляторы будут делать бессмысленные вещи, когда происходит переполнение со знаком, вместо того, чтобы всегда переполняться одним и тем же образом.   -  person hugomg    schedule 22.09.2014
comment
Да, специфично для C. Например, в Java такого поведения нет. В C целое число без знака переносится, но целое число со знаком вызывает неопределенное поведение. Это может зацикливаться, но не всегда :) Никогда не допускайте переполнения целочисленной арифметики со знаком в C.   -  person ouah    schedule 22.09.2014
comment
Чтобы подчеркнуть то, что сказал @hugomg, вы можете проверить, как gcc превратил конечный цикл в бесконечный цикл из-за переполнения со знаком в вопросе Почему это цикл выдает «предупреждение: итерация 3u вызывает неопределенное поведение» и выводит более 4 строк?   -  person Shafik Yaghmour    schedule 22.09.2014
comment
@ouah: Итак, в C это не работает, я понимаю вашу точку зрения. Но основная мысль этого примера, я думаю, заключается в том, что должно произойти, если мы будем придерживаться основной теории CS. Автор (я думаю, после ваших разъяснений) ошибочно использовал C показать свой пример   -  person Cratylus    schedule 22.09.2014

Ответы (1)


arrow_upward
3
arrow_downward

Вы не можете проверить переполнение целого числа со знаком постфактум, вы должны проверить это до выполнения операции. Это связано с тем, что переполнение целого числа со знаком в арифметической операции является неопределенным поведением в C, а также в C++. Как только вы вызвали неопределенное поведение, результат вашей программы становится непредсказуемым (см. мой комментарий выше для одного из самых неожиданных результатов, которые я видел). Для C это можно увидеть, перейдя к проекту C99. стандартный раздел 6.5 Выражения, в котором говорится:

Если во время вычисления выражения возникает исключительное условие (то есть, если результат не определен математически или не находится в диапазоне представляемых значений для его типа), поведение не определено.

Cert предоставляет надежное руководство о том, как предотвратить переполнение подписи: INT32-C. Убедитесь, что операции с целыми числами со знаком не приводят к переполнению, а для добавления в документе рекомендуется следующий метод:

#include <limits.h>

void f(signed int si_a, signed int si_b) {
  signed int sum;
  if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
      ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
    /* Handle error */
  } else {
    sum = si_a + si_b;
  }
  /* ... */
}

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

person Shafik Yaghmour    schedule 22.09.2014