Berechnung ganzzahliger absoluter Differenzen auf überlaufsichere Weise?

Question

Ich möchte die absolute Differenz von zwei ganzen Zahlen berechnen. Naiv betrachtet ist dies einfach abs(a - b) . Dies ist jedoch mit einigen Problemen verbunden, je nachdem, ob es sich um ganze Zahlen mit oder ohne Vorzeichen handelt:

• Für ganze Zahlen ohne Vorzeichen, a - b eine große positive Zahl sein wird, wenn b größer ist als a und die Absolutwert-Operation wird dies nicht beheben.

• Für ganze Zahlen mit Vorzeichen, a - b kann außerhalb des Bereichs der Werte liegen, die als vorzeichenbehaftete Ganzzahl dargestellt werden können, was zu undefiniertem Verhalten führt. (Dies bedeutet natürlich, dass das Ergebnis eine ganze Zahl ohne Vorzeichen sein muss.)

Wie können diese Probleme auf effiziente Weise angegangen werden?

Ich möchte einen Algorithmus (oder ein Paar von Algorithmen), der sowohl für vorzeichenbehaftete als auch für vorzeichenlose Ganzzahlen funktioniert und sich nicht auf die Umwandlung der Werte in eine größere Ganzzahlgröße stützt.

(Um das klarzustellen: meine Frage ist nicht, wie man das in Code schreibt, sondern was genau ich schreiben sollte, um Überlaufsicherheit zu garantieren. Berechnung abs(a - b) als vorzeichenbehafteter Wert und anschließendes Casting auf einen vorzeichenlosen Wert funktioniert nicht, da ein Überlauf einer vorzeichenbehafteten Ganzzahl zumindest in C normalerweise eine undefinierte Operation ist).

Answer 1

(Ich habe das selbst herausgefunden, nachdem ich die Frage gestellt hatte - ich dachte, es wäre schwieriger, und ich würde mich immer noch über andere Antworten freuen, wenn es bessere gibt!)

Die Lösung für ganze Zahlen ohne Vorzeichen ist relativ einfach (wie in der Antwort von Jack Toole beschrieben) und funktioniert, indem die (implizite) Bedingung außerhalb der Subtraktion verschoben wird, so dass wir immer die kleinere Zahl von der größeren subtrahieren und nicht einen potenziell eingeschlossenen Wert mit Null vergleichen:

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

Damit bleibt nur noch die Frage der vorzeichenbehafteten ganzen Zahlen. Betrachten Sie die folgende Variante:

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

Wir können leicht beweisen, dass dies mit Hilfe der Modulo-Arithmetik funktioniert. Wir wissen, dass a y (unsigned) a sind kongruent modulo UINT_MAX . Außerdem ist die vorzeichenlose ganzzahlige Subtraktionsoperation kongruent zur tatsächlichen Subtraktion modulo UINT_MAX Kombiniert man diese Fakten, so weiß man, dass (unsigned) a - (unsigned) b ist kongruent mit dem tatsächlichen Wert von a - b modulo UINT_MAX . Schließlich, weil wir wissen, dass der tatsächliche Wert von a - b muss zwischen 0 y UINT_MAX-1 wissen wir, dass dies eine exakte Gleichheit ist.

Answer 2

Bearbeitet, um Brook Moses' Fix für signierte Typen und Kerrek SB's make_unsigned zu verwenden, um für Verwendung von Vorlagen.

Erstens können Sie entweder das folgende für make_unsigned verwenden, oder Sie können std::make_unsigned , tr1::make_unsigned , oder BOOST::make_unsigned verwenden.

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;};

Dann wird die Vorlagendefinition zu einer einfachen:

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);
}

Wie Brooks Moses erklärt, ist dieser Wraparound sicher.

Answer 3

Hier ist eine Idee: Wenn wir vorzeichenlos sind, nehmen wir einfach die richtige Differenz. Wenn wir vorzeichenbehaftet sind, geben wir den entsprechenden vorzeichenlosen Typ zurück:

#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);
}

Verwendung: int a, b; unsigned int d = absdiff(a, b);

Answer 4

Code:

#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;
}

Ausgabe:

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