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

[vak]

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

int add(int a, int b);

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

Comments

[borisk]

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

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

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

[mopexod]

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

[borisk]

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

[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 даёт ответ, но не объясняет, как его получить.

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

[caztd]

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

[vak]

Это правильный подход, но нам нужны люди, умеющие реализовать этот самый __builtin_add_overflow() на стандартном Си.

[vit_r]

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

[juan_gandhi]

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

[vit_r]

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

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

[dluciv]

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

[archaicos]

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

[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.

[juan_gandhi]

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

[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;
}

[archaicos]

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

[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.

[ex0_planet]

С вычитанием прикольнее.

Но вообще задачка проверяет не столько знание Си, сколько умение искать информацию :-)

[archaicos]

Большинство тупо не знает что искать. Им говоришь, что есть проблема в "a+b", или спрашиваешь, нет ли в тут проблемы. И они глазами хлоп-хлоп. Искать можно уже только к следующему собеседованию.

[vak]

Задачка проверяет знакомство с понятием Undefined Behavior. А если у кандидата представление о UB имеется, это большой плюс в карму. Ну и ещё нужно немного умения рассуждать логически.

[spamsink]

Кто все эти безумные люди, которые рассуждают про unsigned, какие-то там детали реализации каких-то там конкретных версий языков программирования, про битовые операции, 2's complement представление? Какая нахер разница? Машина может быть хоть троичная симметричная, и не иметь понятия об "unsigned".

Пятикласснику должно быть понятно, что достаточно знать только MAX и MIN для данного типа операндов, и делается это так: нарочно не на языке программирования, а на естественном языке.

1. Если хотя бы одно из чисел равно нулю или числа с разным знаком, то складываем без опаски.
2. Если оба числа положительные, то вычтем из MAX одно из них. Если разность меньше другого числа, то бросаем исключение.
3. Если оба числа отрицательные, то вычтем из MIN одно из них. Если разность больше другого числа, то бросаем исключение.
4. Складываем числа, возвращаем результат.

По-хорошему, спрашивать надо про
template< typename T > int add(const T & a, const T & b); и вопрос тогда будет про type traits (который синтаксис я так и не запомнил).

[vak]

Вот, именно такой ответ и ожидается. Даже код писать не обязательно.

Не, тепмплейты на собеседовании это уже издевательство. :) В такую контору я бы и сам не пошёл.

[caztd]

Ну если уж на то пошло, то машина может и не иметь концепта арифметического переполнения или MAX/MIN для определенного типа операндов. Поэтому совсем от машины абстрагироваться не получится.

А уж если мы говорим про язык Си, то мы обычно говорим об этом не для красоты, а для того чтоб писать эффективный и быстрый код. Потому что если вам не нужен такой код, то зачем вам Си? Берите Питон или JS какой-нибудь в самом деле. Ну а если вам нужен эффективный и быстрый код, то вам никогда-никогда не следует использовать вышеуказанный алгоритм для пятиклассников. Потому что он медленный, плохо-читается,
в нем легко сделать ошибку, которую потом будет трудно найти.

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