Определяет ли вычитание целых чисел без знака поведение?

100

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

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

Это единственная неопределенно релевантная цитата из стандарта C, которую я смог найти.

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

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

т.е.

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

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

0x0000 - 0x0001 == (без знака) (0 + -1) == (0xFFFF, но также 0xFFFE или 0x8001)

Какая или какая интерпретация верна? Это вообще определяется?

LihO
источник
3
Выбор слов в стандарте неудачный. То, что он «никогда не может переполниться», означает, что это не ошибка. Используем стандартную терминологию, вместо того, чтобы переполнять значение «обертывания».
данортон

Ответы:

107

Результат вычитания, генерирующего отрицательное число в типе без знака, четко определен:

  1. [...] Вычисление с участием беззнаковых операндов никогда не может быть переполнено, потому что результат, который не может быть представлен результирующим целочисленным типом без знака, уменьшается по модулю числа, которое на единицу больше наибольшего значения, которое может быть представлено результирующим типом. (ИСО / МЭК 9899: 1999 (E) §6.2.5 / 9)

Как видите, (unsigned)0 - (unsigned)1равно -1 по модулю UINT_MAX + 1, или, другими словами, UINT_MAX.

Обратите внимание, что, хотя в нем говорится: «Вычисление с использованием беззнаковых операндов никогда не может переполниться», что может привести вас к мысли, что оно применяется только для превышения верхнего предела, это представлено как мотивация для фактической связывающей части предложения: «a результат, который не может быть представлен результирующим целочисленным типом без знака, уменьшается по модулю числа, которое на единицу больше наибольшего значения, которое может быть представлено результирующим типом ". Эта фраза не ограничивается выходом за верхнюю границу типа и в равной степени применяется к значениям, слишком низким для представления.

бдонлан
источник
2
Спасибо! Теперь я вижу интерпретацию, которой мне не хватало. Я думаю, они могли бы выбрать более четкую формулировку.
4
Я чувствую себя намного лучше, зная , что если какие - либо без знака сложения катается до нуля и вызывает хаос, то это будет , потому что uintвсегда был предназначен для представления математического кольца целых чисел 0через UINT_MAX, с операциями сложения и умножения по модулю UINT_MAX+1, а не потому , что переполнения. Однако возникает вопрос, почему, если кольца являются таким фундаментальным типом данных, язык не предлагает более общей поддержки для колец других размеров.
Теодор Мердок,
2
@TheodoreMurdock Я думаю, что ответ на этот вопрос прост. Насколько я могу судить, то, что это кольцо, - следствие, а не причина. Реальное требование состоит в том, что все биты беззнаковых типов должны участвовать в представлении значения. Из этого естественно вытекает кольцевое поведение. Если вы хотите, чтобы такое поведение происходило от других типов, выполните арифметические операции, а затем примените требуемый модуль; который использует фундаментальные операторы.
underscore_d
@underscore_d Конечно ... понятно, почему они приняли дизайнерское решение. Просто забавно, что они написали спецификацию примерно как «нет арифметического переполнения / потери значимости, потому что тип данных указан как кольцо», как если бы этот выбор конструкции означал, что программистам не нужно тщательно избегать чрезмерного и недостаточного -flow или их программы резко проваливаются.
Теодор Мердок
121

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

введите описание изображения здесь

9 + 4 = 1 ( 13 по модулю 12 ), поэтому в другом направлении это: 1-4 = 9 ( -3 по модулю 12 ). Тот же принцип применяется при работе с беззнаковыми типами. Если тип результата - это unsignedмодульная арифметика.


Теперь посмотрим на следующие операции, сохраняющие результат в виде unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Если вы хотите убедиться, что результат есть signed, сохраните его в signedпеременной или приведите к signed. Если вы хотите получить разницу между числами и убедиться, что модульная арифметика не будет применяться, вам следует рассмотреть возможность использования abs()функции, определенной в stdlib.h:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Будьте очень осторожны, особенно при написании условий, потому что:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

но

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...
LihO
источник
4
Хорошая модель с часами, хотя доказательство сделает этот ответ правильным. Предпосылка вопроса уже включает утверждение, что все это может быть правдой.
Гонки легкости на орбите,
5
@LightnessRacesinOrbit: Спасибо. Я написал это, потому что думаю, что это может кому-то пригодиться. Согласен, это не полный ответ.
LihO
4
Линия никуда int d = abs(five - seven);не годится. Сначала five - sevenвычисляется: продвижение оставляет типы операндов как unsigned int, результат вычисляется по модулю (UINT_MAX+1)и оценивается как UINT_MAX-1. Тогда это значение является фактическим параметром для abs, что является плохой новостью. abs(int)вызывает неопределенное поведение при передаче аргумента, поскольку он не входит в диапазон и, abs(long long)вероятно, может содержать значение, но неопределенное поведение возникает, когда возвращаемое значение принудительно intинициализируется d.
Бен Фойгт,
1
@LihO: единственный оператор в C ++, который является контекстно-зависимым и действует по-разному в зависимости от того, как используется его результат, - это пользовательский оператор преобразования operator T(). Сложение в двух обсуждаемых нами выражениях выполняется по типу unsigned intна основе типов операндов. Результат сложения есть unsigned int. Затем этот результат неявно преобразуется в тип, требуемый в контексте, преобразование, которое завершается ошибкой, поскольку значение не может быть представлено в новом типе.
Бен Фойгт,
1
@LihO: Может быть, стоит подумать о double x = 2/3;vsdouble y = 2.0/3;
Бен Фойгт,
5

Что ж, первая интерпретация верна. Однако ваши рассуждения о «подписанной семантике» в этом контексте неверны.

Опять же, ваша первая интерпретация верна. Беззнаковая арифметика подчиняется правилам арифметики по модулю, что означает, что для 32-битных беззнаковых типов выполняется 0x0000 - 0x0001оценка 0xFFFF.

Однако для получения того же результата требуется и вторая интерпретация (основанная на «семантике со знаком»). Т.е. даже если вы выполняете оценку 0 - 1в домене подписанного типа и получаете -1промежуточный результат, это -1все равно необходимо произвести, 0xFFFFкогда позже он будет преобразован в беззнаковый тип. Даже если на какой-то платформе используется экзотическое представление для целых чисел со знаком (дополнение до единицы, величина со знаком), эта платформа по-прежнему должна применять правила арифметики по модулю при преобразовании целочисленных значений со знаком в беззнаковые.

Например, эта оценка

signed int a = 0, b = 1;
unsigned int c = a - b;

по - прежнему гарантированно производить UINT_MAXв c, даже если платформа использует экзотическое представление для целых чисел.

Муравей
источник
4
Я думаю, вы имеете в виду 16-битные беззнаковые типы, а не 32-битные.
xioxox 03 окт.15,
4

С беззнаковыми числами типа unsigned intили больше, при отсутствии преобразований типов, a-bопределяется как выдача беззнакового числа, которое при добавлении к нему bдаст a. Преобразование отрицательного числа в беззнаковое определяется как получение числа, которое при добавлении к исходному числу с обратным знаком даст ноль (поэтому преобразование -5 в беззнаковое даст значение, которое при добавлении к 5 даст ноль) .

Обратите внимание, что числа без знака, меньшие, чем unsigned intмогут быть переведены в тип intдо вычитания, поведение a-bбудет зависеть от размера int.

суперкар
источник