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

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

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)

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

Ответ 1

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

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

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

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

Ответ 2

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

9 + 4 = 1 (13 mod 12), поэтому в другом направлении это: 1 - 4 = 9 (-3 mod 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)
    // ...

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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