C безопасно принимает абсолютное значение целого числа

Как педантичный программист предохранится от этого, не делая никаких предположений, не гарантированных стандартом?

Один из методов заключается в использовании целых чисел без знака. Поведение переполнения целых чисел без знака четко определено, как и поведение при преобразовании целого числа со знаком в целое число без знака.

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

uintmax_t j = i;
if (j > (uintmax_t)INTMAX_MAX) {
  j = -j;
}
printf("Result: |%jd| = %ju\n", i, j);

Так как же это работает?

uintmax_t j = i;

Это преобразует целое число со знаком в беззнаковое. ЕСЛИ оно положительное, значение остается прежним, если отрицательное, значение увеличивается на 2ⁿ (где n – количество битов). Это преобразует его в большое число (больше, чем INTMAX_MAX)

if (j > (uintmax_t)INTMAX_MAX) {

Если исходное число было положительным (и, следовательно, меньше или равно INTMAX_MAX), это ничего не делает. Если исходное число было отрицательным, выполняется внутренняя часть блока if.

  j = -j;

Число отрицается. Результат отрицания явно отрицательный и поэтому не может быть представлен как целое число без знака. Таким образом, оно увеличивается на 2ⁿ.

Итак, алгебраически результат для отрицательного i выглядит так

j = - (i + 2ⁿ) + 2ⁿ = -i

Умное, но это решение делает предположения. Это не удается, если INTMAX_MAX == UINTMAX_MAX, что разрешено стандартом C.

Хм, давайте посмотрим на это (я читаю https://busybox.net/~landley/c99-draft.html, который, по-видимому, является последним черновиком C99 до стандартизации, если что-то изменилось в окончательном стандарте, пожалуйста, сообщите мне.

Когда определены имена typedef, отличающиеся только отсутствием или наличием начального u, они должны обозначать соответствующие типы со знаком и без знака, как описано в 6.2.5; реализация не должна предоставлять тип без предоставления соответствующего типа.

В 6.2.5 вижу

Для каждого целочисленного типа со знаком существует соответствующий (но другой) целочисленный тип без знака (обозначенный ключевым словом unsigned), который использует тот же объем памяти (включая информацию о знаке) и имеет те же требования к выравниванию.

В 6.2.6.2 вижу

#1

Для целочисленных типов без знака, отличных от unsigned char, биты представления объекта должны быть разделены на две группы: биты значения и биты заполнения (последние не обязательно должны быть). Если имеется N битов значения, каждый бит должен представлять разную степень числа 2 от 1 до 2N-1, так что >объекты этого типа должны быть способны представлять значения от 0 до 2N-1 >используя чисто двоичное представление; это должно быть известно как представление значения. Значения любых битов заполнения не указаны.39)

#2

Для целочисленных типов со знаком биты представления объекта должны быть разделены на три группы: биты значения, биты заполнения и бит знака. Не должно быть битов заполнения; должен быть ровно один бит знака. Каждый бит, являющийся битом значения, должен иметь то же значение, что и тот же бит в объектном представлении соответствующего беззнакового типа (если имеется M битов значения в знаковом типе и N в беззнаковом типе, тогда M‹=N). Если знаковый бит равен нулю, это не должно влиять на результирующее значение.

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

Хорошо, основываясь на приведенном выше анализе, обнаружившем недостаток в моей первой попытке, я написал более параноидальный вариант. Это имеет два изменения по сравнению с моей первой версией.

Я использую i ‹ 0 вместо j > (uintmax_t)INTMAX_MAX для проверки отрицательных чисел. Это означает, что алгоритм выдает правильные результаты для чисел, больших или равных -INTMAX_MAX, даже если INTMAX_MAX == UINTMAX_MAX.

Я добавляю обработку для случая ошибки, когда INTMAX_MAX == UINTMAX_MAX, INTMAX_MIN == -INTMAX_MAX -1 и i == INTMAX_MIN. Это приведет к j=0 внутри условия if, которое мы можем легко проверить.

Из требований стандарта C видно, что INTMAX_MIN не может быть меньше -INTMAX_MAX -1, так как имеется только один бит знака, а количество битов значения должно быть таким же или меньшим, чем в соответствующем беззнаковом типе. Просто не осталось битовых шаблонов для представления меньших чисел.

uintmax_t j = i;
if (i < 0) {
  j = -j;
  if (j == 0) {
    printf("your platform sucks\n");
    exit(1);
  }
}
printf("Result: |%jd| = %ju\n", i, j);

@plugwash Я думаю, что 2501 правильный. Например, значение -UINTMAX_MAX становится равным 1: (-UINTMAX_MAX + (UINTMAX_MAX + 1)), и оно не перехватывается вашим if. - Хайд 58 минут назад

ммм,

предполагая, что INTMAX_MAX == UINTMAX_MAX и i = -INTMAX_MAX

uintmax_t j = i;

после этой команды j = -INTMAX_MAX + (UINTMAX_MAX + 1) = 1

if (i < 0) {

i меньше нуля, поэтому мы запускаем команды внутри if

j = -j;

после этой команды j = -1 + (UINTMAX_MAX + 1) = UINTMAX_MAX

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

Если результат imaxabs не может быть представлен, это может произойти при использовании дополнения до двух, тогда поведение не определено.

7.8.2.1 Функция imaxabs

2. Функция imaxabs вычисляет абсолютное значение целого числа j. Если результат не может быть представлен, поведение не определено. 221)

221) Абсолютное значение самого отрицательного числа не может быть представлено в дополнении до двух.

Проверка, которая не делает предположений и всегда определена:

intmax_t i = ... ;
if( i < -INTMAX_MAX )
{
    //handle error
}

(Этот оператор if нельзя использовать, если используется представление дополнения или знака, поэтому компилятор может выдать предупреждение о недоступности кода. Сам код по-прежнему определен и действителен.)

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

Единственный способ защититься от этого — сравнить ввод с самым отрицательным значением для типа (INTMAX_MIN в коде, который вы показываете).

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

Теперь рассмотрим умножение целого числа на 3: Здесь у нас гораздо более серьезная проблема. Эта операция вызывает неопределенное поведение в 2/3 всех случаев! А для двух третей всех значений x int найти int со значением 3x просто невозможно. Это гораздо более серьезная проблема, чем проблема абсолютного значения.

Вы можете использовать некоторые битовые хаки:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Это хорошо работает, когда INT_MIN < v <= INT_MAX. В случае, когда v == INT_MIN, остается INT_MIN , не вызывая неопределенного поведения.

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

Ссылка: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

в соответствии с этим http://linux.die.net/man/3/imaxabs

Примечания

Попытка взять абсолютное значение самого отрицательного целого числа не определена.

Чтобы обработать весь диапазон, вы можете добавить что-то подобное в свой код.

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

редактировать: поскольку abs(INTMAX_MIN) не может быть представлено на машине с дополнением до 2, 2 значения в пределах представляемого диапазона объединяются на выходе в виде строки. Протестировано с помощью gcc, хотя для printf требуется %lld, поскольку %jd не поддерживается форматом.

1. Действительно ли это неопределенное поведение, как в «коду разрешено запускать любой путь кода, который любой код, который нравится компилятору», когда пользователь вводит неверный номер? Или это какой-то другой аромат не совсем определенного?

Поведение программы не определено только тогда, когда неверное число успешно введено и передано в imaxabs(), что в типичной системе дополнения до 2 возвращает результат -ve, как вы заметили.

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

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

Настоящая проблема с этим неопределенным поведением заключается в том, что оптимизирующий компилятор может отбросить наивные проверки, поэтому код вроде:

r = (i < 0) ? -i : i;
if (r < 0) {   // This code may be pointless
    // Do overflow recovery
    doRecoveryProcessing();
} else {
    printf("%jd", r);
}

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

2. Как педантичный программист предохранится от этого, не делая никаких предположений, не гарантированных стандартом?

Безусловно, лучший способ - просто убедиться, что программа работает в допустимом диапазоне, поэтому в этом случае достаточно проверки ввода (запретить INTMAX_MIN). Программы, печатающие таблицы abs(), должны избегать INT*_MIN и т.д.

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

По-видимому, выписывает абс (INTMAX_MIN) подделкой, позволяя программе выполнить обещание, данное пользователю.