Переполнение со знаком целочисленного значения в C ++?
У меня есть устаревшая кодовая база, с которой мы пытаемся перейти devtoolset-4 в devtoolset-7, Я заметил интересное поведение в отношении переполнения целых чисел со знаком (int64_t, чтобы быть конкретным).
Существует фрагмент кода, который используется для обнаружения переполнения целых чисел при умножении большого набора целых чисел:
// a and b are int64_t
int64_t product = a * b;
if (b != 0 && product / b != a) {
// Overflow
}
Этот код работал нормально с devtoolset-4. Однако с devtoolset-7 переполнение никогда не обнаруживается.
Например: когда a = 83802282034166 а также b = 98765432,
product становится -5819501405344925872 (явно значение переполнено).
Но product / b приводит к значению, равному a (83802282034166), Следовательно if состояние никогда не становится истинным.
Его значение должно быть рассчитано на основе переполнения (отрицательный) product значение: -5819501405344925872 / 98765432 = -58922451788
По иронии судьбы математика верна, но она вызывает аномальное поведение в отношении devtoolset-4.
- Может ли компилятор кэшировать значение (а не переоценивать его), что приводит к такому поведению?
- Или оптимизация компилятора преобразует заявление
product / b != a
вproduct != a * bи достигает того же переполненного значения (или, возможно, просто пропускает вычисления, основанные на приведенном выше утверждении, гдеproduct = a * b)?
Я понимаю, что целочисленное переполнение со знаком является «неопределенным поведением» в C ++, и поэтому поведение компилятора может меняться в разных реализациях. Но может ли кто-нибудь помочь мне разобраться в вышеуказанном поведении?
Примечание: версии g ++ в devtoolset-4 и devtoolset-7 g++ (GCC) 5.2 а также g++ (GCC) 7.2.1соответственно.
Решение
Поскольку подписанное переполнение / недополнение классифицируется как неопределенное поведение, компиляторам разрешено обманывать и предполагать, что это не может произойти (это произошло во время выступления на Cppcon год или два назад, но я забываю это из головы). Поскольку вы выполняете арифметику и затем проверяете результат, оптимизатор получает возможность оптимизировать часть проверки.
Это непроверенной код, но вы, вероятно, хотите что-то вроде следующего:
if(b != 0) {
auto max_a = std::numeric_limits<int64_t>::max() / b;
if(max_a < a) {
throw std::runtime_error{"overflow"};
}
}
return a * b;
Обратите внимание, что этот код не обрабатывает недопущение; если a * b может быть отрицательным, эта проверка не будет работать.
в Godbolt, Вы можете видеть, что ваша версия полностью оптимизирована.
Другие решения
Целочисленное переполнение со знаком — неопределенное поведение в C ++.
Это означает, что оптимизатор может предположить, что этого никогда не произойдет. a*b/b является a, период.
Современные компиляторы выполняют статическую оптимизацию на основе одного назначения.
// a and b are int64_t
int64_t product = a * b;
if (b != 0 && product / b != a) {
// Overflow
}
будет выглядеть так:
const int64_t __X__ = a * b;
const bool __Y__ = b != 0;
const int64_t __Z__ = __X__ / b;
const int64_t __Z__ = a*b / b;
const int64_t __Z__ = a;
if (__Y__ && __Z__ != a) {
// Overflow
}
который оценивает
if (__Y__ && false) {
// Overflow
}
ясно, как __Z__ является a а также a!=a является false,
int128_t big_product = a * b;
работать с big_product и обнаружить переполнение там.
SSA позволяет компилятору реализовать такие вещи, как (a+1)>a всегда верно, что может упростить многие циклы и случаи оптимизации. Этот факт основывается на том факте, что переполнение значений со знаком является неопределенным поведением.
Со знанием того, чтоproduct == a * bкомпилятор / оптимизатор может предпринять следующие шаги по оптимизации:
b != 0 && product / b != a
b != 0 && a * b / b != a
b != 0 && a * 1 != a
b != 0 && a != a
b != 0 && false
false
Оптимизатор может выбрать удаление ветви полностью.
Я понимаю, что целочисленное переполнение со знаком является «неопределенным поведением» в C ++, и поэтому поведение компилятора может меняться в разных реализациях. Но может ли кто-нибудь помочь мне разобраться в вышеуказанном поведении?
Возможно, вы знаете, что целочисленное переполнение со знаком — это UB, но я полагаю, вы еще не поняли, что на самом деле означает UB. UB не нужно, и часто не имеет смысла. Этот случай кажется прямым, хотя.
Может ли кто-нибудь помочь мне разобраться в вышеуказанном поведении?
Целочисленное переполнение со знаком имеет неопределенное поведение в C ++. Это означает, что вы не можете надежно обнаружить его, и тот код, который содержит целочисленное переполнение со знаком, может Делать что-нибудь.
Если вы хотите определить, приведет ли операция к целочисленному переполнению со знаком или нет, вам нужно сделать это до того, как произойдет переполнение, чтобы предотвратить UB.
Целочисленное переполнение со знаком — неопределенное поведение. Это отличается от unsigned int(все неподписанные целые).
Подробнее об этом here
Как примечание, люди заметили, что использование int вместо unsigned int увеличивает производительность (см. Вот), поскольку компилятор не имеет дело с поведением переполнения.
Если вы беспокоитесь о целочисленных переполнениях, не лучше использовать целочисленную библиотеку произвольной точности — с этим вы можете увеличить размер вашего типа до 128 бит и не беспокоиться об этом.
Вы можете прочитать эту документацию, она может быть вам полезна, как если бы у меня возникли какие-либо проблемы с переменными и типами данных. http://www.cplusplus.com/doc/tutorial/variables/