расстояние между двумя знаковыми числами - PullRequest
0 голосов
/ 30 сентября 2018

Расстояние между двумя числами часто вычисляется следующим образом:

long distance(long x, long y)
{
     return x > y ? x - y : y - x;
}

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

Одним из способов решения этой проблемы является использование беззнакового типа для представления итогового расстояния.Расстояние не может быть отрицательным, поэтому подписанный тип не требуется.Расстояние между минимальным и максимальным типом со знаком должно соответствовать типу без знака одинакового размера.( Edit: Поскольку chux ответил, это не совсем правильное предположение.) Поэтому я действительно изменил первую функцию следующим образом:

unsigned long distance(long x, long y)
{
    return (x > y) ? (unsigned long)x - (unsigned long)y
                   : (unsigned long)y - (unsigned long)x;
}

Теперь он правильно вычисляет расстояние между двумя знаковыми длинными значениями?в стандартном и портативном виде?Если это не так, что бы исправить?

Ответы [ 3 ]

0 голосов
/ 01 октября 2018

Правильно ли теперь рассчитывается расстояние между двумя длинными знаками стандартным и переносимым способом?

Да.

Редкое исключение 1 обязало бы использовать более широкий тип.


Рассмотрим 3 случая, когда x > y

x>= 0, y> = 0

Следующее является тривиально правильным, так как приведение не меняет значение .

(unsigned long)x - (unsigned long)y

x <0,y <0 </strong>

Оба значения x, y увеличиваются на ULONG_MAX + 1 из-за (unsigned long), и вычитание отменяет это.

// is akin to 
((unsigned long)(x + ULONG_MAX + 1) - (unsigned long)(y + ULONG_MAX + 1))
// or
x - y // with unsigned math.

x>= 0, y <0 </strong>

(unsigned long)y имеет значение y + ULONG_MAX + 1, что больше x.(Предполагая ULONG_MAX/2 >= LONG_MAX 1 ) Разница отрицательная.Тем не менее unsigned математика оборачивается и добавляет обратно ULONG_MAX + 1.

// is akin to 
((unsigned long)x - (unsigned long)(y + ULONG_MAX + 1)) + (ULONG_MAX + 1).
// or
x - y // with unsigned math.

x <0, y> = 0

Этот случайневозможно, так как x > y.


1 : C не указывает ULONG_MAX/2 == LONG_MAX, хотя это чрезвычайно распространено.Я только сталкивался с этим однажды давным-давно, где это не применимо.В этом случае это было ULONG_MAX == LONG_MAX.ULONG_MAX/2 == LONG_MAX настолько ожидаемо, что я сомневаюсь, что современная платформа рискнула бы этого не делать.C определяет ULONG_MAX >= LONG_MAX.

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

Код может использовать приведенное ниже для обнаружения этих редких платформ.

#if ULONG_MAX/2 < LONG_MAX
  #error `unsigned long` too narrow.  Need new approach.
#endif
0 голосов
/ 01 октября 2018

при условии, что sizeof (unsigned long long)> sizeof (unsigned long) безопасно объявить его как: unsigned long long distance(long x, long y)

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

0 голосов
/ 30 сентября 2018

Поскольку переполнение без знака (и недополнение) хорошо определено для C и C ++, при использовании арифметики дополнения до 2 ваша измененная функция в порядке.

...