Ответ на задачку по Си

[vak]

Исчерпывающий ответ на задачу сложить два числа дал spamsink : https://vak.dreamwidth.org/659406.html?thread=5230798#cmt5230798

Вот код на Си++, решающий поставленную задачу, не вызывая неопределённого поведения и не прибегая к трюкам.

int add(int a, int b)
{
    int sum;

    if (a >= 0) {
        if (b >= 0) {
            // Оба числа положительные - сместим на верхнюю границу.
            sum = (a - INT_MAX) + b;
            if (sum > 0)
                throw std::overflow_error("Integer overflow");
            sum += INT_MAX;
        } else {
            // Разные знаки, нет переполнения.
            sum = a + b;
        }
    } else {
        if (b >= 0) {
            // Разные знаки, нет переполнения.
            sum = a + b;
        } else {
            // Оба числа отрицательные - сместим на нижнюю границу.
            sum = (a - INT_MIN) + b;
            if (sum < 0)
                throw std::overflow_error("Integer overflow");
            sum += INT_MIN;
        }
    }
    return sum;
}

Как видите, вовсе не теорема Ферма. Not a rocket science, как говорят американцы. Последовательность простых логических рассуждений.

Вот по этой причине физики не любят Си и Си++. Вы даже два числа сложить не можете без фокусов, говорят они. :)

Заметим, что проблема undefined behavior в арифметике свойственна только Си/Си++. Во многих современных языках, таких как Java, Go или Rust, она отсутствует.

Comments

[juan_gandhi]

Я б убавил повторений, а так да, красиво насчет шифта.

Я так понимаю, что (a - INT_MAX) + b > 0 эквивалентно (a+b) < 0. Что, конечно, упрощает эти все вещи.

[archaicos]

Логика вот какая...
Допустим a и b уже >= 0.
Условие переполнения a + b очевидное: a + b > INT_MAX.
Но в C его так в лоб записать нельзя, т.к. это переполнение возникнет в проверке.
Но можно написать if (a > INT_MAX - b) или if (b > INT_MAX - a), и переполнения не возникнет.
Тут можно было бы и остановиться. Но можно переписать в форме
if ((a - INT_MAX) + b > 0) или if ((b - INT_MAX) + a > 0).
И тоже не будет переполнения.

[juan_gandhi]

a+b > INT_MAX в си можно написать как a+b < 0.

[archaicos]

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

[juan_gandhi]

Ах вон как. Ну тогда ладно, тогда шифт - единственное решение.

[vak]

Повторения - мать-перемать учения, как говаривал один майор у нас на военной кафедре. :)

[ircicq]

Решение предполагает что INT_MAX ≤ |INT_MIN| ≤ INT_MAX+1 Есть ли это в стандарте?

[vak]

Вряд ли в стандарте такое записано. Но контр-пример в голову не приходит. Во всех известных мне архитектурах используется или дополнительный код (INT_MIN = -INT_MAX-1), или обратный (INT_MIN = -INT_MAX).

[ircicq]

В таком виде будет работать при любых INT_MIN, INT_MAX:

int add(int a, int b) {
    if (a > 0 && INT_MAX - a < b || a < 0 && INT_MIN - a > b)
        throw overflow_error("arithmetic overflow");
    return a + b;
}

[vak]

Ну вот, отличное решение.

[archaicos]

В (a - INT_MAX) + b при a и b >= 0:
  -INT_MAX <= (a - INT_MAX) <= 0
  Целое со значением -INT_MAX существует всегда.
Т.е. тут прибавляем к неотрицательному b или 0, или отрицательное. Переполнения не возникает.

В (a - INT_MIN) + b при a и b < 0:
   0 <= (a - INT_MIN) < -INT_MIN - 1
  Целое со значением -INT_MIN - 1 существует всегда.
Т.е. тут аналогично прибавляем к отрицательному b или 0, или положительное, и переполнения не возникает.

Т.е. нет, решение не требует симметрии или его отсутствия в диапазоне целых. Спасает то, что в самом начале проверки a и b такие: >= 0 и <0, т.е. что нет проверки a <= 0.
а = 0 в (a - INT_MIN) дало бы переполнение в коде дополнения до двух (и не дало бы в двух других представлениях целых со знаком).

[spamsink]

Вот-вот. Никто не гарантирует соотношение абсолютных величин INT_MIN и INT_MAX, поэтому теоретически вычитание INT_MAX из нуля может привести к UB. Так что вычитать всегда нужно из соответствующего максимума. Я ж не зря в том комменте сформулировал именно так, как я это сделал.

[archaicos]

-INT_MAX можно всегда. Не всегда можно -INT_MIN (обычно нельзя).

[spamsink]

Это у тебя взгляд узкий, поэтому ты и думаешь, что всегда. Вон, я в VHDL объявлю какой-нибудь целый тип как integer range (-3 to 4), и синтезатор будет в полном праве отвести под него всего 3 бита.

[archaicos]

Вопрос же по C/C++, а там три возможных варианта для представления целых чисел со знаком. Два симметричны: -INT_MAX==INT_MIN. А один нет: -INT_MAX==INT_MIN+1. И именно этот один наиболее представлен в природе сегодня.
А так-то, можно изобрести чо угодно. И без VHDL.

[spamsink]

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

[vak]

Проблема легко решается вставкой дополнительных проверок наподобие "if (a == 0) return b;". Но это непрактично, так как архитектуры, отличные от 2's complement и 1's complement, не встречаются в природе.

[norian]

по идее вообще железо должно ставить флаг и кидать ивент при переполнении

и это будет точно быстрее работать :о))

[vak]

Это верно, и многие языки так и делают, начиная с Фортрана. Но не Си.

[norian]

вообще странная ситуация - самый железный йазыг не может просто и понятно работать с железом

можно конечно зафигачть что-нть вроде
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);

но это будет и платформозависимо и компайлерзависимо, то есть вообще кошерно нихт, пардон май котеговский

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

[waqur]

Гм, а я так понял ответ spamsink, что он предлагает такое решение:

int add(int a, int b)
{
    if (a >= 0) {
        if (b >= 0) {
            // Оба числа положительные
            if (INT_MAX - a < b)
                throw std::overflow_error("Integer overflow");
        } else {
            // Разные знаки, нет переполнения
        }
    } else {
        if (b >= 0) {
            // Разные знаки, нет переполнения
        } else {
            // Оба числа отрицательные
            if (INT_MIN - a > b)
                throw std::overflow_error("Integer overflow");
        }
    }
    return a + b;
}

И его, кстати, можно дальше оптимизировать.
Например, так:

int add(int a, int b)
{
    if (a >= 0) {
        if (INT_MAX - a < b)
            throw std::overflow_error("Integer overflow");
    } else {
        if (INT_MIN - a > b)
            throw std::overflow_error("Integer overflow");
    }
    return a + b;
}

[vak]

Да, так компактнее выходит. Выше ircicq ужал код вообще до трёх строчек: https://vak.dreamwidth.org/659576.html?thread=5236856#cmt5236856

Re: int add(int a, int b)

[dememax]

Про Си/Си++: ну, да, нет исключений на переполнения. Но почему бы в этом случае не использовать другой язык (тот же Фортран) и слинковаться с результатом.

А ещё, это же не единственная "проблема Си/Си++".
Я в последнее время открыл для себя санитайзеры, так там есть соответствующая возможность обнаружить такие вещи - "-fsanitize=signed-integer-overflow".

Санитайзеры

[vak]

Санитайзеры полезная штука, да. Не всегда помогают, впрочем. В моём нынешнем проекте вся память выделяется динамически, и санитайзеры не ловят. Боремся посредством классических assert().

Re: память выделяется динамически

[dememax]

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

Re: память выделяется динамически

[vak]

В простых случаях valgrind справляется, но нам не помог. Слишком много он всякого мусора выдаёт, в этих терабайтах хрен разберёшься.

Re: память выделяется динамически

[dememax]

О, это - тема, конечно.
"Нормальные проекты" сами поставляют для своих пользователей файлы подавления нежелательных сообщений (gstreamer, glib, ...).
А потом, зря вы юнит-тесты пишите что ли!?
Самый простой тест (типа, создали компонент) уже может дать возможность для создания файла подавления или нахождения самых банальных ошибок (либо убедиться, что их нет).
Понятное дело, что если все тесты запускать - то "туши свет", особенно если много фолс позитивз.
"Разделяй и властвуй!"