Есть ли безопасный способ получить абсолютное значение без знака целого числа со знаком без запуска переполнения?

Рассмотрим типичную функцию абсолютного значения (где для аргумента интегральный тип максимального размера длинный):

unsigned long abs(long input);

Наивная реализация этого может выглядеть примерно так:

unsigned long abs(long input)
{
    if (input >= 0)
    {
        // input is positive
        // We know this is safe, because the maximum positive signed
        // integer is always less than the maximum positive unsigned one
        return static_cast<unsigned long>(input);
    }
    else
    {
        return static_cast<unsigned long>(-input); // ut oh...
    }
}

Этот код запускает поведение undefined, потому что отрицание input может переполняться, а инициирование переполнения целых чисел - undefined. Например, на машинах с дополнением 2s абсолютное значение std::numeric_limits<long>::min() будет на 1 больше, чем std::numeric_limits<long>::max().

Что может сделать автор библиотеки для решения этой проблемы?

Ответы

Ответ 1

Сначала можно применить к неподписанному варианту. Это обеспечивает четкое поведение. Если вместо этого код выглядит следующим образом:

unsigned long abs(long input)
{
    if (input >= 0)
    {
        // input is positive
        return static_cast<unsigned long>(input);
    }
    else
    {
        return -static_cast<unsigned long>(input); // read on...
    }
}

мы вызываем две четко определенные операции. Преобразование целочисленного знака в неподписанное значение определено N3485 4.7 [conv.integral]/2:

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

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

Отрицание целого числа без знака хорошо определено в 5.3.1 [expr.unary.op]/8:

Отрицание неподписанной величины вычисляется путем вычитания его значения из 2 ^ n, где n - количество бит в продвинутом операнде.

Эти два требования эффективно заставляют реализации работать как машина с дополнением 2s, даже если базовая машина является 1s-дополнением или сигнальной машиной.

Ответ 2

Просто добавьте один, если отрицательный.

unsigned long absolute_value(long x) {
  if (x >= 0) return (unsigned long)x;
  x = -(x+1);
  return (unsigned long)x + 1;
}