Почему целочисленное переполнение без знака определяется поведением, а переполнение со знаком - нет?

210

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

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

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

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

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

c++ c undefined-behavior integer-overflow Энтони Валле-Дюбуа
источник
50
Возможно, потому что существует более одного способа представления целых чисел со знаком. Какой способ не указан в стандарте, по крайней мере, в C ++.
juanchopanza
Полезная ссылка: en.wikipedia.org/wiki/Signed_number_representations
Робо
7
То, что сказал juanchopanza, имеет смысл. Насколько я понимаю, исходный стандарт Си в значительной степени кодифицировал существующую практику. Если все реализации в то время согласились с тем, что должен делать «переполнение» без знака, это хорошая причина для его стандартизации. Они не сошлись во мнении о том, что должно делать подписанное переполнение, поэтому они не попали в стандарт.
2
@DavidElliman Неподписанный перенос при добавлении также легко обнаруживается ( if (a + b < a)). Переполнение при умножении сложно для типов со знаком и без знака.
5
@DavidElliman: Вопрос не только в том, можете ли вы его обнаружить, но и в результате. В реализации знак + значение MAX_INT+1 == -0, в то время как на дополнении до двух это будетINT_MIN
Дэвид Родригес - dribeas

Ответы:

163

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

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

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

C99 6.2.6.1:3 :

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

C99 6.2.6.2:2 :

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

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

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

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

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

Паскаль Куок
источник
6
Важное замечание здесь заключается в том, что в современном мире не осталось никаких архитектур, использующих что-либо, кроме арифметики со знаком 2-го дополнения. То, что языковые стандарты все еще допускают реализацию, например, на PDP-1, является чисто историческим артефактом.
Энди Росс
9
@AndyRoss, но все еще существуют системы (компиляторы OS +, по общему признанию, со старой историей) со своим дополнением и новыми выпусками по состоянию на 2013 год. Пример: OS 2200.
13
3
@ Энди Росс, не могли бы вы подумать, что «нет архитектур ... использующих что-либо, кроме дополнения 2 ...», сегодня включает в себя весь спектр DSP и встроенных процессоров?
chux - Восстановить Монику
11
@AndyRoss: хотя есть архитектуры «нет», использующие что-либо, кроме дополнения 2s (для некоторого определения «нет»), определенно есть архитектуры DSP, которые используют насыщающую арифметику для целых чисел со знаком.
Стивен Кэнон
10
Насыщенная подписанная арифметика определенно соответствует стандарту. Конечно, инструкции обёртывания должны использоваться для арифметики без знака, но компилятор всегда имеет информацию, чтобы знать, выполняется ли арифметика без знака или со знаком, так что он, безусловно, может выбрать инструкции соответствующим образом.
кафе
15

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

Стоит также отметить, что «неопределенное поведение» не означает «не работает». Это означает, что реализация может делать все, что угодно в этой ситуации. Это включает в себя выполнение «правильных действий», а также «вызов полиции» или «сбой». Большинство компиляторов, когда это возможно, выбирают «поступать правильно», предполагая, что это относительно легко определить (в данном случае это так). Однако, если у вас возникают переполнения в вычислениях, важно понимать, к чему это приводит, и что компилятор МОЖЕТ делать что-то другое, чем вы ожидаете (и это может очень зависеть от версии компилятора, настроек оптимизации и т. Д.) ,

Матс Петерссон
источник
23
Однако компиляторы не хотят, чтобы вы полагались на то, что они поступают правильно, и большинство из них покажет вам это, как только вы скомпилируете int f(int x) { return x+1>x; }с оптимизацией. GCC и ICC, с опциями по умолчанию, оптимизируют вышеуказанное до return 1;.
Паскаль Куок
1
Для примера программы, которая дает разные результаты при intпереполнении в зависимости от уровней оптимизации, см. Ideone.com/cki8nM. Думаю, это демонстрирует, что ваш ответ дает плохой совет.
Магнус Хофф
Я немного исправил эту часть.
Матс Петерссон
Если бы C предоставил средство для объявления целого числа «обертка со знаком двух», ни у одной платформы, которая вообще может запустить C, не должно быть больших проблем, чтобы поддерживать его хотя бы умеренно эффективно. Дополнительных издержек было бы достаточно, чтобы код не использовал такой тип, когда поведение переноса не требуется, но большинство операций над целыми числами дополнения двух идентичны операциям с целыми числами без знака, за исключением сравнений и повышений.
Суперкат
1
Отрицательные значения должны существовать и «работать», чтобы компилятор работал правильно. Конечно, вполне возможно обойти отсутствие значений со знаком в процессоре и использовать значения без знака, как дополняющие или дополняющие два, в зависимости от того, что больше смысл, основанный на том, что набор инструкций. Как правило, это будет значительно медленнее, чем наличие аппаратной поддержки, но оно ничем не отличается от процессоров, которые не поддерживают аппаратное обеспечение с плавающей запятой, или аналогичных - просто добавляется много дополнительного кода.
Матс Петерссон
10

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

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

С11 6,5 / 5

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

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

С11 6.2.5 / 9

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

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

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

С11 6.3.1.3

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

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

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

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

Лундин
источник
6

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

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

Supercat
источник
Я не совсем понимаю - почему это помогает иметь аддитивную обратную зависимость? Я не могу придумать ни одной ситуации, когда поведение переполнения действительно полезно ...
sleske
@sleske: Использование десятичной дроби для удобства чтения, если счетчик энергии показывает 0003, а предыдущее значение было 9995, означает ли это, что использовалось -9992 единицы энергии или 0008 единиц энергии? Наличие 0003-9995 доходности 0008 позволяет легко рассчитать последний результат. Наличие его -9992 сделало бы его немного более неловким. Однако невозможность сделать это тоже приведет к необходимости сравнить 0003 с 9995, заметить, что это меньше, сделать обратное вычитание, вычесть результат из 9999 и добавить 1.
суперкат
@sleske: Для людей и для компиляторов также очень полезно применять ассоциативные, дистрибутивные и коммутативные законы арифметики для переписывания выражений и их упрощения; например, если выражение a+b-cвычисляется в цикле, но bи cявляются постоянными в пределах этого цикла, это может быть полезно , чтобы переместить вычисление (b-c)вне цикла, но делает это потребует среди других вещей , которые (b-c)дают значение , которое, при добавлении к a, даст a+b-c, что, в свою очередь, требует, чтобы cиметь аддитивную обратную.
суперкат
Спасибо за объяснения. Если я правильно понимаю, все ваши примеры предполагают, что вы действительно хотите справиться с переполнением. В большинстве случаев, с которыми я столкнулся, переполнение нежелательно, и вы хотите его предотвратить, потому что результат вычисления с переполнением бесполезен. Например, для счетчика энергии вы, вероятно, хотите использовать такой тип, чтобы переполнение никогда не происходило.
слеське
1
... такой, что (a+b)-cсоответствует a+(b-c)представимости арифметического значения b-cв типе, подстановка будет действительной независимо от возможного диапазона значений для (b-c).
суперкат
1

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

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

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

YTH
источник
Чтобы структура была полем, каждый элемент структуры, кроме аддитивного тождества, должен иметь мультипликативный обратный знак. Структура целых конгруэнтных mod N будет полем, только если N одно или простое [вырожденное поле, когда N == 1]. Ты что-то чувствуешь, что я пропустил в своем ответе?
суперкат
Ты прав. Я запутался в основных силовых модулях. Оригинальный ответ отредактирован.
YTH
Дополнительное заблуждение в том , что там есть поле порядка 2 ^ п, это просто не кольцо изоморфно целых чисел по модулю 2 ^ п.
Кевин Вентулло
И 2 ^ 31-1 - простое число Мерсенна (но 2 ^ 63-1 - не простое число). Таким образом, моя оригинальная идея была разрушена. Кроме того, целые размеры были разными в те времена. Итак, моя идея была в лучшем случае ревизионистской.
YTH
ИМХО, тот факт, что целые числа без знака образуют кольцо (а не поле), взятие части младшего разряда также дает кольцо, и выполнение операций со всем значением, а затем усечение будет вести себя эквивалентно выполнению операций только над нижней частью. почти наверняка соображения.
суперкат