Простая задачка на Си++

[vak]

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

int add(int a, int b);

Удивительно, сколько народу обламывается на этой задачке.

Comments

[borisk]

То есть, заглянуть вот сюда, к примеру:

https://en.cppreference.com/w/cpp/language/try_catch

— выше сил аппликантов?

[mopexod]

Целочисленная арифметика исключений не вызывает.

[caztd]

Типичный пример задачи, которую вредно решать самому.
Короткий гугл-поиск дает ответ (только gcc конечно):

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort(); // or throw;
    return sum;
}

[vit_r]

Вот потому и не могут решить. Copy-paste даёт ответ, но не объясняет, как его получить.

А когда вставляют в код ответ не от той задачи, совсем весело.

[vit_r]

Задача неоднозначно поставлена. Можно преобразовать в длинные, сложить длинные и короткие, а потом сравнить результаты. Что будет правильным ответом, потому что про производительность никто не спрашивал.

[caztd]

Как получить ответ -- это вопрос на экзамене а не для приема на работу.
Первая истина для разработчика -- не умножай сущностей,
то есть не выдумывай заново, то что уже придумано до тебя.
Если человек не нашел builtin'a в гугле, то он уже не квалифицирован для разработки.
И знает ли он о том что signed integer overflow это UB или не знает это уже совершенно неважно.

[vit_r]

Код в сети сейчас такого качества, что проще переписать чем искать в нём ошибки.

[caztd]

Смотря где и какой код. Но в общем и целом нет.

Это как если бы вы сейчас сказали: в сети столько плохо написанных научных статей,
что проще написать свою с нуля, чем изучать existing works.

[vit_r]

Ну, да. Если говорить о китайских статьях, то несомненно.

[waqur]

Ну, задачка не такая уж и простая. :)
Для беззнаковых типичный паттерн проверки на переполнение — это сложить и проверить, что результат сложения не меньше одного из операндов (любого). А для знаковых — не знаю, ветвиться по знаковости операндов нужно, наверное, на все четыре случая. А в ветках - сводить всё к беззнаковым и применять тот же приёмчик. Это в предположении, что просто перейти к типам большей размерности нельзя, например, такая платформа, что sizeof(int) == sizeof(intmax_t).

[waqur]

Вспомнил про флаг OF в интеловской архитектуре x86 и полез в Википедию читать правила его вычисления:

Internally, the overflow flag is usually generated by an exclusive or of the internal carry into and out of the sign bit.

Мило, но вряд-ли аппликант на работу додумается до этого на собеседовании, если не знает заранее.

Carry out of the sign bit можно вычислить, как я уже говорил, после кастинга обоих операндов к unsigned int, их сложения, и сравнения суммы с любым из них, например первым. Если сумма беззнаковых меньше первого беззнакового — значит бит Carry out равен 1, иначе 0.

Carry in можно вычислить, просто применив AND-маску ((unsigned int)(INT_MAX)) к обоим операндам в беззнаковой форме перед сложением. Нужный нам бит "Carry in of the sign bit" будет в старшем бите результата после сложения.

А далее просто XOR этих carry in и carry out, как учит Википедия. :)

Интересно, найдётся ли компилятор, который преобразует все эти извращения обратно в инструкцию чтения флага OF.

[sobriquet9]

Это точно про C++, а не про представление целых чисел? Я думаю, что вот такое будет работать, но не уверена, что оно соответствует стандарту (фиг знает какие ещё могут быть внутренние представления и когда в них выскочит Undefined Behavior)

int add(int a, int b)
{
  int sum = a + b;
  if (a > 0 && b > 0 && sum < -1) {
    throw std::overflow_error("result too positive");
  } else if (a < 0 && b < 0 && sum > -1) {
    throw std::overflow_error("result too negative");
  }
  return sum;
}

[juan_gandhi]

Довольно логично, и не так уж неэффективно.

[juan_gandhi]

Достаточно проверить равенство знаков, и пробовать сложить абсолютные величины.

[waqur]

А как с точки зрения стандарта (C/C++), переполнение знаковых целых — определено? Насколько я помню, для беззнаковых с определённостью переполнений всё было норм, а для знаковых что-то там было нечисто.

Я в курсе, что в процессоре инструкция add одна для всех типов операндов (и знаковых, и беззнаковых, и их комбинаций), я интересуюсь исключительно в контексте того, не съедет ли компилятор с катушек и не вставит ли туда инструкцию ud2, не выбросит ли весь код как недостижимый и т.д.

[juan_gandhi]

Нет смысла спрашивать меня про стандарт. Я его не знаю (да и не знал никогда).

[vit_r]

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

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

[juan_gandhi]

Я когда-то всю эту хрень на форте (т.е. на ассемблере, если кишки брать) программировал.

[borisk]

Вот поэтому я и не программист.

[ircicq]

int add(int a, int b) {
    int sum = a + b;
    if (~(a ^ b) & (a ^ sum) & INT_MIN)
         throw overflow_error("arithmetic overflow");
    return sum;
}

[vak]

Это уже кое-что. Единственная проблема здесь: первая строчка даёт undefined behavior.

[archaicos]

Есть машинки (типа UNISYS Clearpath), у которых только тип char маленький (8 бит), а все остальные целочисленные (в т.ч. short и long) одинаково большие (96 бит).
Т.е. там более длинных целочисленных типов просто нет.

[ircicq]

int add(int a, int b) {
    if (~(a ^ b) & (a ^ ((a & ~INT_MIN) + (b & ~INT_MIN))) & INT_MIN)
        throw overflow_error("arithmetic overflow");
    return a + b;
}

[archaicos]

UB возникает во время +. Потом на результат от этого + смотреть уже поздно.

[archaicos]

Компилятор не со зла что-то делает. Логика такая:
1. undefined behavior не определено никак
2. компилятор не обязан его детектировать (и во многих ситуациях принципиально не может это сделать во время компиляции)
3. компилятор его не детектирует, а просто считает, что его не происходит, что программист не ошибся
4. в данном конкретном случае компилятор посчитает, что переполнения не произойдёт (а если произойдёт, то это undefined behavior же, ну и хер с ним)
5. это ему может открыть пути для оптимизации, т.е. здесь он может выкинуть код, следующий за оператором сложения, который проверяет на переполнение (которого ведь не возникает, а если возникает, то это UB и проблема программиста-недоучки, а не компилятора)