Вычисление целочисленных абсолютных разностей безопасными для переполнения способами - PullRequest
Новая
       7

Вычисление целочисленных абсолютных разностей безопасными для переполнения способами

7 голосов
/ 06 ноября 2011

Я хотел бы вычислить абсолютную разницу двух целых чисел. Наивно это всего лишь abs(a - b). Тем не менее, это имеет несколько проблем, в зависимости от того, являются ли целые числа со знаком или без знака:

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

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

Как можно эффективно решить эти проблемы?

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

(Также, чтобы уточнить: мой вопрос не в том, как написать это в коде, а в том, что именно я должен написать, чтобы гарантировать безопасность переполнения. Вычисление abs(a - b) в качестве значения со знаком и затем приведение к значению без знака не работает, потому что целочисленное переполнение со знаком, как правило, является неопределенной операцией, по крайней мере, в C.)

Ответы [ 4 ]

7 голосов
/ 06 ноября 2011

(Я работал над этим самостоятельно после того, как задал вопрос - я думал, что это будет сложнее, и я все равно буду приветствовать другие ответы, если есть лучшие!)

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

if (a > b)
  return a - b;
else
  return b - a;

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

if (a > b)
  return (unsigned) a - (unsigned) b;
else
  return (unsigned) b - (unsigned) a;

Мы можем легко доказать, что это работает, используя арифметику по модулю.Мы знаем, что a и (unsigned) a являются конгруэнтными по модулю UINT_MAX.Кроме того, операция вычитания целого числа без знака совпадает с фактическим вычитанием по модулю UINT_MAX, поэтому, комбинируя эти факты, мы знаем, что (unsigned) a - (unsigned) b соответствует фактическому значению a - b по модулю UINT_MAX.Наконец, поскольку мы знаем, что фактическое значение a - b должно быть между 0 и UINT_MAX-1, мы знаем, что это точное равенство.

1 голос
/ 06 ноября 2011

Код: 

#include <stdio.h>
#include <limits.h>

unsigned AbsDiffSigned(int a, int b)
{
  unsigned diff = (unsigned)a - (unsigned)b;
  if (a < b) diff = 1 + ~diff;
  return diff;
}

unsigned AbsDiffUnsigned(unsigned a, unsigned b)
{
  unsigned diff = a - b;
  if (a < b) diff = 1 + ~diff;
  return diff;
}

int testDataSigned[] =
{
  { INT_MIN },
  { INT_MIN + 1 },
  { -1 },
  { 0 },
  { 1 },
  { INT_MAX - 1 },
  { INT_MAX }
};

unsigned testDataUnsigned[] =
{
  { 0 },
  { 1 },
  { UINT_MAX / 2 + 1 },
  { UINT_MAX - 1 },
  { UINT_MAX }
};

int main(void)
{
  int i, j;

  printf("Absolute difference of signed integers:\n");

  for (j = 0; j < sizeof(testDataSigned)/sizeof(testDataSigned[0]); j++)
    for (i = 0; i < sizeof(testDataSigned)/sizeof(testDataSigned[0]); i++)
      printf("abs(%d - %d) = %u\n",
             testDataSigned[j],
             testDataSigned[i],
             AbsDiffSigned(testDataSigned[j], testDataSigned[i]));

  printf("Absolute difference of unsigned integers:\n");

  for (j = 0; j < sizeof(testDataUnsigned)/sizeof(testDataUnsigned[0]); j++)
    for (i = 0; i < sizeof(testDataUnsigned)/sizeof(testDataUnsigned[0]); i++)
      printf("abs(%u - %u) = %u\n",
             testDataUnsigned[j],
             testDataUnsigned[i],
             AbsDiffUnsigned(testDataUnsigned[j], testDataUnsigned[i]));
  return 0;
}

Выход: 

Absolute difference of signed integers:
abs(-2147483648 - -2147483648) = 0
abs(-2147483648 - -2147483647) = 1
abs(-2147483648 - -1) = 2147483647
abs(-2147483648 - 0) = 2147483648
abs(-2147483648 - 1) = 2147483649
abs(-2147483648 - 2147483646) = 4294967294
abs(-2147483648 - 2147483647) = 4294967295
abs(-2147483647 - -2147483648) = 1
abs(-2147483647 - -2147483647) = 0
abs(-2147483647 - -1) = 2147483646
abs(-2147483647 - 0) = 2147483647
abs(-2147483647 - 1) = 2147483648
abs(-2147483647 - 2147483646) = 4294967293
abs(-2147483647 - 2147483647) = 4294967294
abs(-1 - -2147483648) = 2147483647
abs(-1 - -2147483647) = 2147483646
abs(-1 - -1) = 0
abs(-1 - 0) = 1
abs(-1 - 1) = 2
abs(-1 - 2147483646) = 2147483647
abs(-1 - 2147483647) = 2147483648
abs(0 - -2147483648) = 2147483648
abs(0 - -2147483647) = 2147483647
abs(0 - -1) = 1
abs(0 - 0) = 0
abs(0 - 1) = 1
abs(0 - 2147483646) = 2147483646
abs(0 - 2147483647) = 2147483647
abs(1 - -2147483648) = 2147483649
abs(1 - -2147483647) = 2147483648
abs(1 - -1) = 2
abs(1 - 0) = 1
abs(1 - 1) = 0
abs(1 - 2147483646) = 2147483645
abs(1 - 2147483647) = 2147483646
abs(2147483646 - -2147483648) = 4294967294
abs(2147483646 - -2147483647) = 4294967293
abs(2147483646 - -1) = 2147483647
abs(2147483646 - 0) = 2147483646
abs(2147483646 - 1) = 2147483645
abs(2147483646 - 2147483646) = 0
abs(2147483646 - 2147483647) = 1
abs(2147483647 - -2147483648) = 4294967295
abs(2147483647 - -2147483647) = 4294967294
abs(2147483647 - -1) = 2147483648
abs(2147483647 - 0) = 2147483647
abs(2147483647 - 1) = 2147483646
abs(2147483647 - 2147483646) = 1
abs(2147483647 - 2147483647) = 0
Absolute difference of unsigned integers:
abs(0 - 0) = 0
abs(0 - 1) = 1
abs(0 - 2147483648) = 2147483648
abs(0 - 4294967294) = 4294967294
abs(0 - 4294967295) = 4294967295
abs(1 - 0) = 1
abs(1 - 1) = 0
abs(1 - 2147483648) = 2147483647
abs(1 - 4294967294) = 4294967293
abs(1 - 4294967295) = 4294967294
abs(2147483648 - 0) = 2147483648
abs(2147483648 - 1) = 2147483647
abs(2147483648 - 2147483648) = 0
abs(2147483648 - 4294967294) = 2147483646
abs(2147483648 - 4294967295) = 2147483647
abs(4294967294 - 0) = 4294967294
abs(4294967294 - 1) = 4294967293
abs(4294967294 - 2147483648) = 2147483646
abs(4294967294 - 4294967294) = 0
abs(4294967294 - 4294967295) = 1
abs(4294967295 - 0) = 4294967295
abs(4294967295 - 1) = 4294967294
abs(4294967295 - 2147483648) = 2147483647
abs(4294967295 - 4294967294) = 1
abs(4294967295 - 4294967295) = 0
1 голос
/ 06 ноября 2011

Вот идея: если мы не подписаны, мы просто берем правильную разницу.Если мы подписаны, мы возвращаем соответствующий тип без знака: 

#include <type_traits>

template <typename T, bool> struct absdiff_aux;

template <typename T> struct absdiff_aux<T, true>
{
  static T absdiff(T a, T b)  { return a < b ? b - a : a - b; }
};

template <typename T> struct absdiff_aux<T, false>
{
  typedef typename std::make_unsigned<T>::type UT;
  static UT absdiff(T a, T b)
  {
    if ((a > 0 && b > 0) || (a <= 0 && b <= 0))
      return { a < b ? b - a : a - b; }

    if (b > 0)
    {
      UT d = -a;
      return UT(b) + d
    }
    else
    {
      UT d = -b;
      return UT(a) + d;
    }
  }
};

template <typename T> typename std::make_unsigned<T>::type absdiff(T a, T b)
{
  return absdiff_aux<T, std::is_signed<T>::value>::absdiff(a, b);
}

Использование: int a, b; unsigned int d = absdiff(a, b);

1 голос
/ 06 ноября 2011

Отредактировано, чтобы использовать исправление Брука Моисея для подписанных типов и make_unsigned Kerrek SB, чтобы позволить использование шаблона.

Во-первых, вы можете использовать следующее для make_unsigned или использовать std :: make_unsigned, tr1 :: make_unsigned или BOOST :: make_unsigned. 

template <typename T> struct make_unsigned { };

template <> struct make_unsigned<bool              > {};
template <> struct make_unsigned<  signed short    > {typedef unsigned short     type;};
template <> struct make_unsigned<unsigned short    > {typedef unsigned short     type;};
template <> struct make_unsigned<  signed int      > {typedef unsigned int       type;};
template <> struct make_unsigned<unsigned int      > {typedef unsigned int       type;};
template <> struct make_unsigned<  signed long     > {typedef unsigned long      type;};
template <> struct make_unsigned<unsigned long     > {typedef unsigned long      type;};
template <> struct make_unsigned<  signed long long> {typedef unsigned long long type;};
template <> struct make_unsigned<unsigned long long> {typedef unsigned long long type;};

Затем определение шаблона становится простым: 

template <typename T>
typename make_unsigned<T>::type absdiff(T a, T b)
{
    typedef typename make_unsigned<T>::type UT;
    if (a > b)
        return static_cast<UT>(a) - static_cast<UT>(b);
    else
        return static_cast<UT>(b) - static_cast<UT>(a);
}

Как объясняет Брукс Моисей, этот обход безопасен.

...