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

Question

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

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)

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

Answer 1

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

9 + 4 = 1 ( 13 mod 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)
    // ...

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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