Почему поведение unsigned integer overflow определено, а signed integer overflow-нет?


переполнение целого числа без знака хорошо определяется стандартами C и c++. Например,стандарт C99 (§6.2.5/9) государств

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

однако, как стандарты утверждают, что переполнение целого числа со знаком является неопределенным поведением. Опять же, от стандарта C99 (§3.4.3/1)

примером неопределенного поведения является поведение при переполнении целого числа

есть ли исторический или (еще лучше!) а техническая причина такого несоответствия?

5 168

5 ответов:

историческая причина заключается в том, что большинство реализаций C (компиляторов) просто использовали любое поведение переполнения, которое было проще всего реализовать с целочисленным представлением, которое оно использовало. В реализациях C обычно используется то же представление, что и ЦП, поэтому поведение переполнения следует из целочисленного представления, используемого ЦП.

на практике, это только представления для значений, которые могут отличаться в зависимости от реализации: дополнения, дополнения two, знак-величина. Для беззнакового типа нет причин, по которым стандарт допускает вариацию, потому что существует только одно очевидное двоичное представление (стандарт допускает только двоичное представление).

соответствующие цитаты:

C99 6.2.6.1: 3:

значения, хранящиеся в битовых полях без знака и объектах типа unsigned char, должны быть представлены с использованием чистой двоичной нотации.

C99 6.2.6.2:2:

Если знаковый бит равен единице, то значение должно быть изменено одним из следующих способов:

- соответствующее значение со знаком бит 0 отрицательная (знак и величину);

- знаковый бит имеет значение - (2N) (два);

- знаковый бит имеет значение - (2N - 1) (один дополнение).


В настоящее время все процессоры используют представление дополнения two, но знаковое арифметическое переполнение остается неопределенным, и разработчики компиляторов хотят, чтобы оно оставалось неопределенным, потому что они используют эту неопределенность для помощи в оптимизации. Например этот блоге Ян Лэнс Тейлор или это жалоба Агнер Фог, и ответы на его сообщение об ошибке.

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

также стоит отметить, что "неопределенное поведение" не означает "не работает". Это означает, что реализация позволено делать все, что угодно в этой ситуации. Это включает в себя "правильную вещь", а также "вызов полиции" или "сбой". Большинство компиляторов, когда это возможно, выберут "делать правильные вещи", предполагая, что это относительно легко определить (в данном случае это так). Однако, если у вас есть переполнения в расчетах, важно понять, что это на самом деле приводит, и что компилятор может сделать что-то другое, чем вы ожидаете (и что это может очень зависеть от компилятора версия, оптимизации параметров и т. д.).

в дополнение к другим упомянутым вопросам, имея беззнаковую математическую оболочку, беззнаковые целочисленные типы ведут себя как абстрактные алгебраические группы (что означает, среди прочего, для любой пары значений X и Y, там будет существовать какое-то другое значение Z такое, что X+Z будет, если правильно разыграть, равной Y и Y-Z будет, если правильно разыграть, равной X). Если беззнаковые значения были просто типами расположения хранилища, а не промежуточными типами выражений (например, если они были нет беззнакового эквивалента самого большого целочисленного типа, и арифметические операции над беззнаковыми типами вели себя так, как если бы они были сначала преобразованы в более крупные подписанные типы, тогда не было бы такой необходимости в определенном поведении обертывания, но трудно выполнять вычисления в типе, который не имеет, например, аддитивного обратного.

это помогает в ситуациях, когда поведение обтекания действительно полезно - например, с порядковыми номерами TCP или определенными алгоритмами, такими как хэш расчет. Это также может помочь в ситуациях, когда необходимо обнаружить переполнение, поскольку выполнение вычислений и проверка переполнения часто проще, чем проверка заранее, будут ли они переполнены, особенно если вычисления включают самый большой доступный целочисленный тип.

прежде всего, обратите внимание, что C11 3.4.3, как и все примеры и примечания к ногам, не является нормативным текстом и поэтому не имеет отношения к цитированию!

соответствующий текст, который утверждает, что переполнение целых чисел и поплавков является неопределенным поведением, таков:

C11 6.5 / 5

Если исключительное условие происходит во время оценки выражение (То есть, если результат не определен математически или не в диапазоне представимых значения для его типа), поведение не определено.

разъяснение относительно поведения беззнаковых целочисленных типов конкретно можно найти здесь:

C11 6.2.5 / 9

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

Это делает целочисленные типы без знака особым случаем.

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

C11 6.3.1.3

6.3.1.3 целые числа со знаком и без знака

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

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

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

возможно, еще одна причина определения беззнаковой арифметики заключается в том, что беззнаковые числа образуют целые числа по модулю 2^n, где n-ширина беззнакового числа. Беззнаковые числа-это просто целые числа, представленные двоичными цифрами вместо десятичных. Выполнение стандартных операций в системе модулей хорошо изучено.

цитата OP ссылается на этот факт, но также подчеркивает тот факт, что существует только один, однозначный, логический способ представления без знака целые числа в двоичном формате. Напротив, подписанные числа чаще всего представлены с использованием дополнения two, но возможны и другие варианты, как описано в стандарте (раздел 6.2.6.2).

представление дополнения Two позволяет некоторым операциям иметь больше смысла в двоичном формате. Например, приращение отрицательных чисел-это то же самое, что и для положительных чисел (ожидайте в условиях переполнения). Некоторые операции на уровне машины могут быть одинаковыми для знаковых и беззнаковых чисел. Однако, при интерпретации результата этих операций некоторые случаи не имеют смысла-положительное и отрицательное переполнение. Кроме того, результаты переполнения различаются в зависимости от базового подписанного представления.