Есть ли вероятность того, что упрощенные формы определенных математических выражений вызовут ошибки переполнения, а сложные — нет?
Я пытался решить задачу №69 для лит-кода, которая включает в себя поиск квадратного корня из заданного числа.
Я применил подход бинарного поиска.
int mySqrt(int x) {
if (x==0 || x==1){
return x;
}
int start =1;
int end=x;
int mid=-1;
while(start<=end){
mid=(end+start)/2;//the problem lies here
long long square=static_cast<long long>(mid)*mid;
if (square>x){
end=mid-1;
}
else if (square==x){
return mid;
}
else{
start=mid+1;
}
}
return static_cast<int>(round(end));
}
Когда я изменил middle=start+(end-start)/2; тестовые примеры прошли нормально, однако для x=2147483647 выдалось «переполнение целого числа со знаком», говоря: «Ошибка времени выполнения: переполнение целого числа со знаком: 2147483647 + 1 не может быть представлено в типе 'инт''.
Да, 2147483647 + 1 переполняется, а 1 + (2147483647 - 1)/2 нет. (И тестовый пример создан специально для того, чтобы вызвать это.) Это известная ошибка в Java SDK, которая оставалась незамеченной в течение многих лет.
Частичный ответ на заданный вопрос: да. Для вашего конкретного случая.... Если start и end оба положительны, и end > start, то (1) end - start представимо как int, а также (end - start)/2 и (2) start + (end - start)/2 находится между start и end, поэтому также никогда не переполняется. Однако (end+start)/2 сначала вычисляет end + start, который (для достаточно больших значений, например start = INT_MAX - 10 и end = INT_MAX - 5) может переполниться. В этом случае поведение не определено — деление на 2 не устраняет волшебным образом последствия переполнения. Вы можете провести аналогичные рассуждения и для других случаев.
Ответы 1
Чтобы ответить на вопрос напрямую: да, разные математически эквивалентные выражения могут давать разные результаты в программе.
В этом случае, если сначала сложить start и end, а затем разделить на 2, если их сумма больше INT_MAX, получится целочисленное переполнение. Однако если вы вычтете start из end, переполнения быть не может, поскольку вы вычитаете два положительных числа.
Однако даже этот подход не совсем корректен, если числа могут быть отрицательными. Предпочитайте использовать std::midpoint (начиная с C++ 20) из заголовка <numeric>, чтобы вообще избежать этих проблем.
#include <numeric>
// ...
mid = std::midpoint(start, end);
@OP - Замена строки кода, вызывающей проблему, на std::midpoint(start, end); решает проблему (принимается Leetcode). Я предлагаю вам принять ответ Unmitigated.
Вы задавали этот вопрос на форумах LeetCode? Если нет, то почему? Если да, пожалуйста, дайте ссылку на это обсуждение здесь, чтобы мы могли прочитать ответы.