Что такое переполнение и зависит ли его определение от языка?

Кратко:

  1. Что такое переполнение и различается ли его определение для разных языков программирования? Например, что мы не считаем переполнением signed-unsigned-приведения в Си++, но считаем в C#?
  2. Можно ли вообще применять термин "переполнение" к действиям с вещественными числами, когда результатом становится бесконечность? Если моя изначальная формулировка про превышение максимального представимого значения верна, то какую роль в ответе играет представимость бесконечности в вещественных типах?

А теперь подробно:

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

C++

Однако при обсуждении вопроса возникла ситуация с подобным кодом на си:

int x = -10;
unsigned y = x;

Два участника сказали мне (раз и два), что этот код не содержит переполнения. В качестве аргументации используется то, что:

  1. Этот код делает битовую копию значения без каких либо вычислений.
  2. Флаги процессора CF и OF при этом не заполняются.

При обдумывании этой ситуации мне пришёл в голову другой аналогичный код:

unsigned x = ~0U;
int y = x; // -1

У такого кода добавляется интересный момент: насколько я знаю, он не содержит UB, однако, знаковое переполнение является UB, поэтому логично заявить, что и переполнения он не содержит. Хотя присваиваемое значение и превышает максимальное значение типа int.

А что если преобразование будет не формальным, а реально присутствующим, например, из вещественного типа?

unsigned x = (unsigned)1e12;

Это всё ещё не переполнение, или уже переполнение?

Компилятор на код

#include <iostream>

using namespace std;

int main()
{
  int x = 1e12;

  cout << x << endl;

  return 0;
}

выдаёт предупрежение

warning: overflow in conversion from ‘double’ to ‘int’ changes value from ‘1.0e+12’ to ‘2147483647’ [-Woverflow]

Получается, такой код он считает переполнением. Впрочем, на UB не похоже, потому что по сути прямо написано, что значение заменяется на максимально допустимое.

Википедия

Википедия содержит две подходящие статьи:

Арифмети́ческое переполне́ние — специфичная для компьютерной арифметики ситуация, когда при арифметическом действии результат становится больше максимально возможного значения для переменной, использующейся для хранения результата.

Я не уверен, что приведение типа можно назвать арифметической операцией...

Целочи́сленное переполне́ние (англ. integer overflow) — ситуация в компьютерной арифметике, при которой вычисленное в результате операции значение не может быть помещено в n-битный целочисленный тип данных. Различают переполнение через верхнюю границу представления и через нижнюю (англ. Underflow).

Под это определение вроде приведение типа бы подходит, но тут есть два нюанса:

  1. При конвертации между int и unsigned битность одинаковая, и в обоих типах значение, как бы, представимо - несмотря на то, что в этих типах это разное значение.

  2. Завязка на целочисленность. Как быть с вариантом

    float x = 1e300;
    

    Тут вообще нет ничего целочисленного, но на мой взгляд выглядит как переполнение. Впрочем, тут ещё один нюанс - получается значение infinity, про которое затруднительно сказать, что оно непредставимо.

C#

А вот если изначальный код написать на C#

checked
{
  int i = -10;
  uint u = (uint)i;
}

То он кидает исключение

System.OverflowException: Arithmetic operation resulted in an overflow.

Получается, что для C# во-первых, это переполнение, а во-вторых, он рассматривает приведение типа как арифметическую операцию.

В то же время с вещественными числами его всё устраивает:

checked
{
  Console.WriteLine((float)1e300);
}
Infinity

Zig

Zig на код

const std = @import("std");
const builtin = @import("builtin");

pub fn main() !void {
    const x: i32 = -10;
    const y: u32 = x;
    
    std.debug.print("Zig {}\n", .{builtin.zig_version});
    std.debug.print("x {}\n", .{x});
    std.debug.print("y {}\n", .{y});
}

выводит ошибку

error: type 'u32' cannot represent integer value '-10'

но при этом не называет произошедшее переполнением.


Вопросы были в самом начале :)


Ответы (1 шт):

Автор решения: Serge3leo

Поскольку “определение”, с математической точки зрения, ограничено документом в котором оно используется, то и определение понятия “переполнения” для разных языков программирования может быть различным. Далее рассмотрим, что такое переполнение в С/С++.

Начнём со второго вопроса, благо С/С++ предполагает возможность реализации IEC 60559 (IEEE 754), который писали видные математики.

С23 (ISO/IEC 9899:2023) в случае IEC 60559 (IEEE 754):

  • Переполнение (FE_OVERFLOW/Overflow) это исключение, которое возникает при выполнении тех или иных операций, которое, по умолчанию, регистрируется во флагах статуса и/или, возможно, вызывает прерывание программы;
  • Обычные операции (+/addition(x, y), fma()/fusedMultiplyAdd(x, y, z) или , sqrt()/squareRoot(x)…), а так же приведение целого типа к плавающему типу convertFromInt(int), должны выполнятся “абсолютно точно”, а результат округляться. При этом, как результат округления, может получиться ±∞;
  • В случае, если при округлении получается ±∞, возникает исключение переполнения. Как следствие, для операций с точным результатом равным ±∞, например, 0 + +∞ -> +∞ такового исключения не возникает;
  • Для операций преобразования к целому, таких как lround()/convertToIntegerTiesToAway(source) и др., при невозможности представления в указанном целом формате, возникает исключение некорректной операции (FE_INVALID/Invalid operation);
  • Доступ к флагам статуса исключений с плавающей точкой (fetestexcept(), feclearexcept(), …) гарантируется, если прагма FENV_ACCESS “on”;
  • Исключения с плавающей точкой должны учитываться в константных выражениях, если прагма FENV_ACCESS “on”;
  • Указывается зависимыми от реализации (Unspecified behavior):
    • Состояние флагов статуса исключений с плавающей точкой при передаче управления между частями с прагмой FENV_ACCESS “on” и “off”;
    • Результат при преобразовании плавающего к целому, если возникло исключение некорректной операции (FE_INVALID/Invalid operation);

С23 (ISO/IEC 9899:2023) безотносительно к IEC 60559 (IEEE 754):

  • Указывается зависимыми от реализации (Unspecified behavior):
    • Результат округления, если значение выходит за границы диапазона;
    • Результат функций lrint(), llrint(), lround() и llround(), если значение непредставимо соответствующим типом;

C++23 (ISO/IEC 14882:2023) холодно ссылается на актуальный ISO C.

Итого ответ на второй вопрос:

  • Можно применять термин "переполнение" к действиям с плавающими числами, даже когда результатом может становится бесконечность (можно опросить флаги статуса исключений);
  • Ваша изначальная формулировка про превышение максимального представимого значения в случае преобразования плавающего типа к целым типам неверна;
  • Правда, в некоторых редких случаях, преобразования целых типов к плавающим типам, например unsigned long к float16_t/binary16, может возникать именно переполнение.

Относительно первого вопроса, к сожалению, ни C23, ни C++23 не содержат явного определения “переполнения” применительно к целым типам. Однако, “По плодам их узнаете их”.

Слово “overflow” встречается в С23 (ISO/IEC 9899:2023) всего на 42 страницах из 742, причём те из них, которые относятся к целым типам, описывают арифметические операции или вычисления выражений. Кроме, быть может, примечания к clock(void), но и там, скорее всего имеются ввиду переполнения при внутренних вычислениях.

С другой стороны, п. 6.3.1.3 описывает преобразование из знакового целого типа в беззнаковый без использования понятия “переполнения”. И обратное преобразование из беззнакового в знаковый, так же описывается без использования понятия “переполнения”, но как зависимое от реализации с возможным возникновением сигнала неопределённой природы.

Таким образом, с целым переполнениям дела обстоят примерно так же, как и с плавающим переполнением и, более менее, обоснованным ответом на первый вопрос в части C/C++ будет:

  • беззнаковых переполнений не бывает, т.к. операции выполняются по модулю 2n;
  • целые переполнения могут возникать при арифметических операциях и вычислении выражений целых знаковых типов;
  • при преобразованиях между беззнаковыми и знаковыми целыми переполнений нет, но может возникать сигнал определяемый реализацией (соответственно, реализация его вправе назвать как угодно, в т.ч. и “overflow”, но это название уже за пределами языка С/С++).

В части реализаций можно отметить:

  • clang поддерживает прагму FENV_ACCESS, поэтому в рамках C/C++ сравнительно легко доступны любые способы обработки любых исключений плавающей точки;
  • gcc не поддерживает прагму FENV_ACCESS, поэтому всё непросто. Можно ли обрабатывать исключение в константных выражениях, лично мне, совсем неясно. Опрашивать флаги статуса надо с оглядкой на оптимизатор, по базе volatile и т.п. нет, но тот же NumPy справляется. Ну или, как вариант, для исключения FE_INVALID включать работу сигнала SIGFPE с помощью feenableexcept(), _controlfp_s() или какой-то матери в зависимости от платформы.

-- Для экспериментов:

#define _GNU_SOURCE 

#include <assert.h>
#include <fenv.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

#ifndef NOT_FENV_ACCESS
    #pragma STDC FENV_ACCESS ON
#endif

#ifndef USE_FEENABLEEXCEPT
    #define FEENABLEEXCEPT(excepts)
#else
    #define FEENABLEEXCEPT(excepts) feenableexcept(excepts)

    #if defined(__APPLE__) && defined(__MACH__)
        // Public domain polyfill for feenableexcept on OS X
        // http://www-personal.umich.edu/~williams/archive/computation/fe-handling-example.c

        #include <fenv.h>

        static
        inline int feenableexcept(unsigned int excepts)
        {
            static fenv_t fenv;
            unsigned int new_excepts = excepts & FE_ALL_EXCEPT;
            // previous masks
            unsigned int old_excepts;

            if (fegetenv(&fenv)) {
                return -1;
            }
            old_excepts = fenv.__control & FE_ALL_EXCEPT;

            // unmask
            fenv.__control &= ~new_excepts;
            fenv.__mxcsr   &= ~(new_excepts << 7);

            return fesetenv(&fenv) ? -1 : old_excepts;
        }
    #elif defined(_WIN32)
        // https://stackoverflow.com/a/30175525/8585880

        void feenableexcept(uint16_t fpflags){
            /*edit 2015-12-17, my attempt at ASM code was giving me
             *problems in more complicated scenarios, so I
             *switched to using _controlfp_s. I finally posted it here
             *because of the upvote to the ASM version.*/
            /*{// http://stackoverflow.com/questions/247053/
             uint16_t mask(FE_ALL_EXCEPT & ~fpflags);
             asm("fldcw %0" : : "m" (mask) : "cc");
            } //https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html   */
            unsigned int new_word(0);
            if (fpflags & FE_INVALID) new_word |= _EM_INVALID;
            if (fpflags & FE_DIVBYZERO) new_word |= _EM_ZERODIVIDE;
            if (fpflags & FE_OVERFLOW) new_word |= _EM_OVERFLOW;
            unsigned int cw(0);
            _controlfp_s(&cw,~new_word,_MCW_EM);
        }
    #endif
#endif

void outtestexcept()
{
  int e = fetestexcept(-1);
  int unknown = ~(FE_DIVBYZERO|FE_INEXACT|FE_INVALID|FE_OVERFLOW|FE_UNDERFLOW);

  printf("%s%s%s%s%s%s\n",
          (e&FE_DIVBYZERO ? "FE_DIVBYZERO " : ""),
          (e&FE_INEXACT   ? "FE_INEXACT "   : ""),
          (e&FE_INVALID   ? "FE_INVALID "   : ""),
          (e&FE_OVERFLOW  ? "FE_OVERFLOW "  : ""),
          (e&FE_UNDERFLOW ? "FE_UNDERFLOW " : ""),
          (e&unknown      ? "unknown "      : "")
        );
}

int main()
{
    feclearexcept(-1);
    FEENABLEEXCEPT(~FE_INEXACT);

    feclearexcept(-1);
    const unsigned long cx = 1e20;

    outtestexcept();
    printf("cx: %lu\n", cx);

    feclearexcept(-1);
    unsigned long x = 1e20;

    outtestexcept();
    printf("x: %lu\n", x);

    double dr = rand() + 1e20;
    assert(dr >= 1e20);

    feclearexcept(-1);
    x = dr;
    outtestexcept();
    printf("%lg -> %lu\n", dr, x);

    feclearexcept(-1);
    x = lround(dr);
    outtestexcept();
    printf("%lg lround %lu\n", dr, x);

    for(int i = 0; i < 4; i++) {
        feclearexcept(-1);
        dr *= 1e100;
        outtestexcept();
        printf("%lg\n", dr);
    }

    return 0;
}
→ Ссылка