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

Question

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

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

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

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

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

Answer 1

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

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

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

C99 6.2.6.1:3:

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

C99 6.2.6.2:2:

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

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

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

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

---

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

Answer 2

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

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

Answer 3

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

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

С11 6,5/5

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

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

С11 6.2.5/9

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

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

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

С11 6.3.1.3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

The most technical reason of all, is simply that trying to capture overflow in an unsigned integer requires more moving parts from you (exception handling) and the processor (exception throwing).

C and C++ won't make you pay for that unless you ask for it by using a signed integer. This isn't a hard-fast rule, as you'll see near the end, but just how they proceed for unsigned integers. In my opinion, this makes signed integers the odd-one out, not unsigned, but it's fine they offer this fundamental difference as the programmer can still perform well-defined signed operations with overflow. But to do so, you must cast for it.

Because:

• unsigned integers have well defined overflow and underflow
• casts from signed -> unsigned int are well defined, is conceptually added to negative values, to map them to the extended positive number range
• casts from unsigned -> signed int are well defined, [uint's name]_MAX - 1 is conceptually deducted from positive values beyond the signed type's max, to map them to negative numbers)

You can always perform arithmetic operations with well-defined overflow and underflow behavior, where signed integers are your starting point, albeit in a round-about way, by casting to unsigned integer first then back once finished.

      int32_t x = 10;
int32_t y = -50;  

// writes -60 into z, this is well defined
int32_t z = int32_t(uint32_t(y) - uint32_t(x));

Casts between signed and unsigned integer types of the same width are free, if the CPU is using 2's compliment (nearly all do). If for some reason the platform you're targeting doesn't use 2's Compliment for signed integers, you will pay a small conversion price when casting between uint32 and int32.

But be wary when using bit widths smaller than int

usually if you are relying on unsigned overflow, you are using a smaller word width, 8bit or 16bit. These will promote to signed int at the drop of a hat (C has absolutely insane implicit integer conversion rules, this is one of C's biggest hidden gotcha's), consider:

      unsigned char a = 0;  
unsigned char b = 1;
printf("%i", a - b);  // outputs -1, not 255 as you'd expect

To avoid this, you should always cast to the type you want when you are relying on that type's width, even in the middle of an operation where you think it's unnecessary. This will cast the temporary and get you the signedness AND truncate the value so you get what you expected. It's almost always free to cast, and in fact, your compiler might thank you for doing so as it can then optimize on your intentions more aggressively.

      unsigned char a = 0;  
unsigned char b = 1;
printf("%i", (unsigned char)(a - b));  // cast turns -1 to 255, outputs 255

Answer 7

C++ просто унаследовал это поведение от C.

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

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

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

Если вы прочитаете обоснование стандарта C на https://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf , где они обсуждают выбор семантики продвижения, они решили, что «сохранение ценности» семантика была безопаснее, однако они приняли это решение, основываясь на предположении, что большинство реализаций использовали двойное дополнение и незаметно обрабатывали перенос очевидным образом.

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

Как только срабатывает неопределенное поведение, «все может случиться». На практике это означает, что значение, которое на самом деле содержит переменная, может быть за пределами диапазона значений, которые компилятор предполагает, что она может содержать. Это, в свою очередь, может сделать проверку границ неэффективной.