Большая часть написанного и еще не написанного кода любой программы так или иначе работает с числами. Вычисление по каким-либо формулам, увеличение или уменьшение счетчиков итераций циклов, рекурсивных вызовов, элементов контейнеров — работа с числами везде.
Компьютер не может напрямую работать с бесконечно «длинными» числами — хранить все их цифры. Как бы много оперативной памяти у нас ни было — все же она конечна. Да и хранить, и обрабатывать величины, сопоставимые с числом атомов в видимой части вселенной — безнадежное занятие. Так что ограничения типов int64 или int128 не очень нас-то и ограничивают
Тем не менее при выполнении операций над целыми числами мы все же имеем шанс выпасть за пределы допустимого диапазона (например, [-2^31, 2^31-1] для int32), и тут в игру вступают особенности поддержки целых чисел для того или иного языка программирования, а также, быть может, особенности реализации конкретной платформы.
При выполнении инструкции add (iadd) платформы х86 переполнение целого числа сопровождается выставлением специального флага переполнения, а результирующее значение просто получается отбрасыванием старшего бита результата. И следует ожидать, что по окончании работы условной программы
x = 2^31 - 1
iadd x 5
произойдет перенос разряда в знаковый бит, и переменная x примет отрицательное значение.
В реализации конкретного языка программирования может быть проверка флага переполнения и сообщение об ошибке. А может и не быть. Может быть гарантия «цикличности» значений (после 2^31-1 идет -2^31), а может и не быть.
Проверки и гарантии — это дополнительные инструкции, которые нужно генерировать компилятору, а процессору потом исполнять.
В языке C++ решили не жертвовать производительностью и заставлять компиляторы генерировать код проверки, а объявили переполнение целых знаковых (signed) чисел неопределенным, открывая простор для оптимизаций. Компилятор может генерировать любой код, какой ему вздумается, ориентируясь лишь на одно правило: переполнения не бывает.
Многие программисты свято верят, что переполнение чисел работает, как ожидается, «циклично» — и пишут проверки вида
if (x > 0 && a > 0 && x + a <= 0) {
// обработай переполнение
}Но, увы, это неопределенное поведение. И компилятор имеет полное право выкинуть такую проверку.
Искусственный пример может быть недостаточно убедительным, так что обратим внимание на следующую, вполне серьезную, функцию вычисления полиномиального хэша строки:
int hash_code(std::string s) {
int h = 13;
for (char c : s) {
h += h * 27752 + c;
}
if (h < 0) h += std::numeric_limits<int>::max();
return h;
}Функция, которая никогда не должна, по задумке, возвращать отрицательные числа, таки выдает отрицательное число! Из-за неопределенного поведения и бессмысленной с точки зрения компилятора проверки.
Другой замечательный, но искусственный пример, для большего устрашения: конечный цикл может стать бесконечным!
// пример взят из блога https://mohitmv.github.io/blog/Shocking-Undefined-Behaviour-In-Action/
int main() {
char buf[50] = "y";
for (int j = 0; j < 9; ++j) {
std::cout << (j * 0x20000001) << std::endl;
if (buf[0] == 'x') break;
}
}Компилятор выполняет удивительную оптимизацию умножения константы на последовательные числа, полностью изменяя заголовок цикла и условия остановки:
for(int j = 0; j < 9*0x20000001; j += 0x20000001) {
...
} а j < 9*0x20000001 всегда истинно так как правая часть больше чем std::numeric_limits<int>::max().
С современными версиями компиляторов этот пример особенно занятен. GCC в подобных циклах иногда способны заметить переполнение и выдать предупреждение. Но этого не произошло...
Однако если мы закомментируем недостижимый break и buf мы получим
<source>:6:37: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
6 | std::cout << (j * 0x20000001) << std::endl;
| ^
<source>:5:23: note: within this loop
5 | for (int j = 0; j < 9; ++j) {
Если раскомментировать объявление buf, то предупреждение пропадет (GCC 13.2)
Другой, возможно, более известный и иногда полезный пример оптимизации, которую такое неопределенное поведение упрощает для компилятора -- сворачивать известные суммы.
Например, при суммировании арифметических прогрессий и некоторых других известных рядов, Clang 12, генерирует совершенно разный код для знаковых и беззнаковых чисел:
// https://godbolt.org/z/oE7q6WjTv
// суммируем квадраты от 1 до N
int64_t summate_squares(int64_t n) {
int64_t sum = 0;
for (int64_t i = 1; i <= n; ++i) {
sum += i * i;
};
return sum;
}
/* Tут нет цикла: используется известная формула (N * (N + 1)) * (2N + 1) / 6,
но довольно сложным способом
summate_squares(long): # @summate_squares(long)
test rdi, rdi
jle .LBB2_1
lea rax, [rdi - 1]
lea rcx, [rdi - 2]
mul rcx
mov r8, rax
mov rsi, rdx
lea rcx, [rdi - 3]
mul rcx
imul ecx, esi
add edx, ecx
shld rdx, rax, 63
movabs rax, 6148914691236517206
shld rsi, r8, 63
imul rax, rdx
lea rcx, [rsi + 4*rsi]
add rcx, rax
lea rax, [rcx + 4*rdi]
add rax, -3
ret
.LBB2_1:
xor eax, eax
ret
*/
uint64_t usummate_squares(uint64_t n) {
uint64_t sum = 0;
for (uint64_t i = 1; i <= n; ++i) {
sum += i * i;
};
return sum;
}
/* А тут цикл есть: переполнение беззнаковых определено и требует обработки
usummate_squares(unsigned long): # @usummate_squares(unsigned long)
test rdi, rdi
je .LBB3_1
mov ecx, 1
xor eax, eax
.LBB3_4: # =>This Inner Loop Header: Depth=1
mov rdx, rcx
imul rdx, rcx
add rax, rdx
add rcx, 1
cmp rcx, rdi
jbe .LBB3_4
ret
.LBB3_1:
xor eax, eax
ret
*/GCC 13 на данный момент (2024 год) в принципе не делает таких оптимизаций по умолчанию. При этом последнии версии Clang 18 уже способны свернуть цикл суммирования квадратов и для беззнаковых:
# https://godbolt.org/z/WqaeaPjfe
usummate_squares(unsigned long): # @usummate_squares(unsigned long)
test rdi, rdi
je .LBB3_1
inc rdi
cmp rdi, 3
mov r8d, 2
cmovae r8, rdi
lea rax, [r8 - 2]
lea rcx, [r8 - 3]
mul rcx
mov rsi, rax
mov rcx, rdx
lea rdi, [r8 - 4]
mul rdi
imul edi, ecx
add edx, edi
shld rdx, rax, 63
movabs rax, 6148914691236517206
shld rcx, rsi, 63
imul rax, rdx
lea rcx, [rcx + 4*rcx]
add rcx, rax
lea rax, [rcx + 4*r8]
add rax, -7
ret
.LBB3_1:
xor eax, eax
retЧитатели, искушенные в теории колец вычетов, могут для беззнаковой версии написать более простой и короткий ассемблерный код в качестве упражнения (нужно лишь правильно поделить на 6)
Корректные проверки переполнения в арифметических операциях намного сложнее чем просто смена знака.
Так, для C++20, безопасный обобщенный код арифметических операций над целыми знаковыми числами мог бы выглядеть так
#include <concepts>
#include <type_traits>
#include <variant>
#include <limits>
namespace safe {
// Все эти проверки справедливы только для целых знаковых чисел
template <class T>
concept SignedInteger = std::is_signed_v<T>
&& std::is_integral_v<T>;
enum class ArithmeticError {
Overflow,
ZeroDivision
};
template <SignedInteger I>
using ErrorOrInteger = std::variant<I, ArithmeticError>;
template <SignedInteger I>
ErrorOrInteger<I> add(I a, // выключаем вывод параметра шаблона по
std::type_identity_t<I> b) // второму аргументу
{
if (b > 0 && a > std::numeric_limits<I>::max() - b) {
// положительное переполнение
return ArithmeticError::Overflow;
}
if (b < 0 && a < std::numeric_limits<I>::min() - b) {
// отрицательное переполнение
return ArithmeticError::Overflow;
}
return a + b;
}
template <SignedInteger I>
ErrorOrInteger<I> sub(I a, std::type_identity_t<I> b) {
if (b < 0 && a > std::numeric_limits<I>::max() + b) {
// положительное переполнение
return ArithmeticError::Overflow;
}
if (b > 0 && a < std::numeric_limits<I>::min() + b) {
// отрицательное переполнение
return ArithmeticError::Overflow;
}
return a - b;
}
template <SignedInteger I>
ErrorOrInteger<I> mul(I a, std::type_identity_t<I> b) {
if (a == 0 || b == 0) {
return 0;
}
if (a > 0) {
if (b > 0) {
if (a > std::numeric_limits<I>::max() / b) {
return ArithmeticError::Overflow;
}
} else {
if (b < std::numeric_limits<I>::min() / a) {
return ArithmeticError::Overflow;
}
}
} else {
if (b > 0) {
if (a < std::numeric_limits<I>::min() / b) {
return ArithmeticError::Overflow;
}
} else {
if (b < std::numeric_limits<I>::max() / a) {
return ArithmeticError::Overflow;
}
}
}
return a * b;
}
template <SignedInteger I>
ErrorOrInteger<I> div(I a, std::type_identity_t<I> b) {
if (b == 0) {
return ArithmeticError::ZeroDivision;
}
if (a == std::numeric_limits<I>::min() && b == -1) {
// диапазон [min, max] несимметричный относительно 0.
// abs(min) > max — будет переполнение
return ArithmeticError::Overflow;
}
return a / b;
}
template <SignedInteger I>
ErrorOrInteger<I> mod(I a, std::type_identity_t<I> b) {
if (b == 0) {
return ArithmeticError::ZeroDivision;
}
if (b == -1) {
// По стандарту в этом случае также неопределенное поведение при
// a == std::numeric_limits<I>::min
// поскольку остаток и неполное частное от деления,
// например, на платформе x86
// получаются одной и той же инструкцией div (idiv),
// что потребует дополнительной обработки.
//
// Но совершенно ясно, что остаток от деления чего угодно на -1 равен 0
return 0;
}
return a % b;
}
}Если вам не нравится возвращать ошибку или результат, можете использовать исключения.
Видно, что безопасные версии арифметических операций должны быть как минимум в два раза медленнее своих исходно небезопасных версий. Такая экономия тактов может быть оправдана, если вы разрабатываете, например, математическую библиотеку и вся ваша производительность упирается в CPU и перемалывание чисел.
Однако, если ваша программа только и делает, что ожидает и выполняет IO операции, то траты в два раза большего числа тактов на сложение или умножение никто и не заметит. Да и язык C++ для таких программ чаще всего не лучший выбор.
Итак, если вы работаете только лишь с беззнаковыми числами (unsigned), то с неопределенным поведением при переполнении никаких проблем нет — все определено как вычисления по модулю 2^N (N — количество бит для выбранного типа чисел).
Если же вы работаете со знаковыми числами, либо используйте безопасные обертки, сообщающие каким-либо образом об ошибках. Либо выводите ограничения на входные данные программы целиком таким образом, чтобы переполнения не возникало, и не забывайте эти ограничения проверять. Все просто, да?
Для выведения ограничений вам помогут отладочные assert с правильными проверками переполнения, которые нужно написать. Или включение ubsan (undefined behavior sanitizer) при сборке компиляторами clang или gcc.
А также тестовые constexpr вычисления.
Также проблемы неопределенного поведения при переполнении касаются битовых сдвигов влево для отрицательных чисел (или при сдвиге положительного числа с залезанием в знаковый бит). Начиная с C++20, стандарт требует фиксированной единой реализации отрицательных чисел — через дополнительный код (two's complement), и многие проблемы сдвигов сняты. Тем не менее все равно стоит следовать общей рекомендации: любые битовые операции выполнять только в unsigned типах.
Стоит заметить, что сужающее преобразование из целочисленного типа в другой целочисленный тип к неопределенному поведению не приводит, и выполнять побитовое и с маской перед присваиванием переменной меньшего типа не обязательно. Но желательно, чтобы избежать предупреждений компилятора
constexpr int x = 12345678;
constexpr uint8_t first_byte = x; // Implicit cast. WarningОчень неприятным является переполнение целых, возникающее из-за правил integer promotion:
constexpr std::uint16_t IntegerPromotionUB(std::uint16_t x) {
x *= x;
return x;
}
// 65535 * 65535 mod 1<<16 = 1
static_assert(IntegerPromotionUB(65535) == 1); // won't compileНесмотря на то, что для беззнаковых переполнение определено как взятие остатка по модулю 2^n и мы используем только беззнаковую переменную,
из-за integer promotion в этом примере возникает переполнение знакового! числа и вытекающее из этого UB. Справедливости ради, надо заметить, что такое происходит только на платформах, где размер int больше uint16_t (то есть практически везде в наши дни).
x *= x; // переписывается как x = x * x;
// тип uint16 меньше чем тип int — для * выполняется неявное приведение к int.