Положительные целые числа, умножающиеся на отрицательное значение

Ответ 1

Существуют ли такие возможные значения для целого, что предварительные условия в порядке, но пост-условие не?

Да, есть несколько входных значений, которые могут привести к поломке сообщения. Если, например,

int a = length*width;

переполняет положительный диапазон int (std::numeric_limits<int>::max()), а реализация компилятора дает отрицательное значение для этого случая.

Как отмечалось в ответах других, ситуация, когда length*width выходит за пределы от ]0-std::numeric_limits<int>::max()[, на самом деле представляет собой поведение undefined, а пост-условие просто бесполезно, потому что для .

Ключевой момент, чтобы исправить это, приведен в @Deduplicator answer, потребности в предварительном условии для улучшения.

В качестве копья для рассуждений Бьярна Страуструпа, чтобы привести этот пример:

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

Ответ 2

Нет, нет никаких значений, которые будут в пределах определенного поведения стандартного С++ нарушать пост-условие. Тем не менее, есть значения, которые все еще могут привести к неправильной работе функции, а именно значения настолько велики, что их продукт не вписывается в целое число. Попробуйте пройти 200'000 и 15'000.

Из-за того, как большинство компиляторов реализует С++, вы можете заметить, что пост-условие нарушено, но то, что вы на самом деле наблюдаете, - это поведение undefined из-за переполнения целых чисел.

Ответ 3

Ответ заключается в том, что его предварительная проверка не завершена. Хотя это слишком ограничительно.
Он не смог включить проверку того, что продукт может быть представлен вместо того, чтобы привести к UB:

int area(int length, int width) {
    // calculate area of a rectangle
    assert(length >= 0 && width >= 0 && (!width
        || std::numeric_limits<int>::max() / width >= length));
    int a = length * width;
    assert(a >= 0); // Not strictly neccessary - the math is easy enough
    return a;
}

Ответ 4

Что приходит мне на ум - это переполнение. Это поведение undefined, но может дать отрицательное значение.
Попробуйте std::numeric_limits<int>::max() и 2.

Ответ 5

Да, если вы используете 16-битный компьютер, так что int = 2B Максимальное значение +32767, поэтому в следующих

{
    length = 500, width = 100;
    if (length<=0 || width <=0) error("area() pre-condition");
    int a = length*width;   // a = 500 * 100 = 50000
    if (a<=0) error("area() post-condition");
    return a;
}

теперь окончательное значение будет a = -17233, потому что оно получает значение -ve. поэтому второе условие получает false.

Все зависит от диапазона.

Ответ 6

INT_MAX не сможет выполнить пост-условие при использовании как длины, так и ширины для всех соответствующих компиляторов.

Возможно, возникает соблазн сказать, что, поскольку стандарт гарантирует, что INT_MAX >= 32767, тогда INT_MAX*INT_MAX всегда будет больше, чем INT_MAX и, следовательно, не будет отображаться в int, который определяется как способный для сохранения максимального значения INT_MAX.
Это хороший аргумент, и на самом деле это происходит чаще всего, вы получите переполнение с большинством компиляторов.

Но чтобы охватить все базы, нам нужно знать, что С++ standard утверждает:

3.4.3
1 undefined поведение
поведение при использовании непереносимой или ошибочной программной конструкции или ошибочных данных, для которых настоящий международный стандарт не налагает никаких требований

2 ПРИМЕЧАНИЕ. Возможное поведение undefined варьируется от полного игнорирования ситуации с непредсказуемыми результатами, ведения во время трансляции или выполнения программы документированным образом, характерным для окружающей среды (с выдачей диагностического сообщения или без него), до прекращения перевода или выполнения (с выдачей диагностического сообщения).

3 ПРИМЕР Пример поведения undefined - это поведение при переполнении целых чисел.

Так что это немного более серьезно, чем не получить правильное значение для области. Когда INT_MAX используется как для длины, так и для ширины (или любой другой комбинации с результатом, который не является представимым), нет гарантии того, что сделает скомпилированная программа. Все может случиться; от вероятных, например переполнения или сбоев, к маловероятным, например, форматам диска.

Ответ 7

Умножение значений, которые переполняют представление битов типа значения, составляет undefined, поскольку количество переполненных бит может быть больше 1. Таким образом, вы можете получить положительный или отрицательный знаковый бит, а количество потерянных битов - переменное.

Пример 1: INT_MAX * 2: результат верен, но поскольку старший бит представляет бит знака, он не исправляется для его типа.

Пример 2: INT_MAX * 4: 1 бит потерян до переполнения, а бит знака неправильный, как в предыдущем примере.

Пример 3: (INT_MAX + 1) * 2 = 0: из-за переполнения всех установленных битов, но знак правильный.

Я использую 8-битное двоичное представление, чтобы было легче читать, чтобы показать, почему это происходит.

0111 1111              // Max positive signed value
+1
1000 0000              // Sign bit set but binary value is correct
*2
0000 0000              // Upper bit is lost due to overflow

В этом случае есть как мягкое переполнение, так и потерянная информация, но представление неверно. И жесткое переполнение, когда бит больше не присутствует в результате.

Разница в переполнении заключается в том, как можно обнаружить переполнение. Обычно жесткие переполнения будут обнаружены аппаратными средствами и требуют очень небольшой работы для программного обеспечения. Однако переполнение программного обеспечения может потребовать, чтобы программное обеспечение явно проверяло условие переполнения, поскольку аппаратное обеспечение обычно не распознает знаковый бит в целых математических операциях.

Как библиотека времени выполнения обрабатывает переполнение до библиотеки. Большинство будет игнорировать это, потому что это быстрее сделать, тогда как другие могут выдать ошибку. Поведение Undefined не означает, что он может отформатировать ваш диск. Результат математической операции никак не изменяет поток кода, за исключением того, что диктует логика кода. Он может игнорировать переполнение или попытаться каким-то образом обработать его. Стандарт не определяет, какой метод использовать, если код или аппаратное обеспечение пытается решить проблему.

В принципе три возможны три вещи, которые могут случиться.
 1. Переполнение игнорируется, а возвращаемое значение недействительно.
 2. Переполнение игнорируется библиотекой времени выполнения, но аппаратное обеспечение выдает ошибку, которая также игнорируется, что приводит к жесткому сбою работающего кода. В этой ситуации полностью зависит от ОС, чтобы определить, что будет дальше. Переход на орехи и уничтожение данных приведет к плохим проектным решениям.
 3. Переполнение обрабатывается библиотекой времени выполнения, которая должна определять наилучший способ продолжения. Как правило, это означает, что код дает возможность поймать ошибку и обработать ее, или, по возможности, вывести код как можно более изящный.

Ответ 8

Так как С++ 11 существует логическое значение, которое вы можете проверить:

std::numeric_limits<int>::is_modulo

Если это значение true, то арифметика с подпиской ведет себя в полном порядке, и в исходном коде нет поведения undefined. Отрицательное значение действительно может быть произведено, и поэтому тест в исходном коде имеет смысл.

Для дальнейшего обсуждения is_modulo см. здесь

Ответ 9

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

Ваше предварительное условие не является полным, и ваше постусловие также недействительно. Не только вы можете получить отрицательные значения, но и положительные значения, которые меньше размера входного значения, все, что вам нужно, - это достаточно большие значения в качестве входных данных, так что обтекание выходит за пределы нуля, т.е. Длинное обтекание.

Вы можете использовать this:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

для защиты от переполнения, но тогда вы захотите использовать дополнительные проверки для FALSE-Positives.

В качестве альтернативы, если производительность не так важна, вы можете использовать библиотеку MPZ. Если производительность является проблемой, и вы хотите написать сборку для CPU с флагом переполнения, вы можете сделать именно это. Возможно, ваш компилятор также может выполнить проверки для вас, например. g++ имеет fno-strict-overflow или может быть передан в unsigned int после проверки предварительного условия.

Во всяком случае, большинство из этих решений фактически не решают вашу проблему, результаты будут foo, то есть вы можете получить меньшую площадь, чем фактический результат.

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