Wie erkenne ich einen Überlauf bei der Multiplikation vorzeichenloser Ganzzahlen?

Question

Ich habe ein Programm in C++ geschrieben, um alle Lösungen von a b \= c , donde a , b y c zusammen alle Ziffern 0-9 genau einmal verwenden. Das Programm durchlief eine Schleife über Werte von a y b und führte jedes Mal eine Ziffernzählroutine auf a , b y a b um zu prüfen, ob die Ziffernbedingung erfüllt wurde.

Allerdings können falsche Lösungen erzeugt werden, wenn a b die Ganzzahlgrenze überschreitet. Ich endete Überprüfung für diese mit Code wie:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

Gibt es eine bessere Möglichkeit, auf Überlauf zu testen? Ich weiß, dass einige Chips ein internes Flag haben, das gesetzt wird, wenn ein Überlauf auftritt, aber ich habe noch nie gesehen, dass man über C oder C++ darauf zugreifen kann.

---

Beachten Sie, dass unterzeichnet int Überlauf ist undefiniertes Verhalten in C und C++ Man muss sie also aufspüren, ohne sie zu verursachen. Für den Überlauf von vorzeichenbehafteten Ints vor der Addition, siehe Erkennung von vorzeichenbehafteten Überläufen in C/C++ .

Answer 1

Ich sehe, dass Sie ganze Zahlen ohne Vorzeichen verwenden. Per Definition, in C (Ich weiß nicht, wie es in C++ ist), die vorzeichenlose Arithmetik läuft nicht über ... also ist Ihr Punkt zumindest für C überflüssig :)

Bei vorzeichenbehafteten ganzen Zahlen, sobald ein Überlauf stattgefunden hat, undefiniertes Verhalten (UB) aufgetreten ist und Ihr Programm alles Mögliche tun kann (z. B.: Tests als nicht schlüssig erklären). 

#include <limits.h>

int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* Unreliable test */
  /* ... */
}

Um ein konformes Programm zu erstellen, müssen Sie auf Überlauf testen vor die diesen Überlauf erzeugen. Die Methode kann auch mit ganzen Zahlen ohne Vorzeichen verwendet werden:

// For addition
#include <limits.h>

int a = <something>;
int x = <something>;
if (x > 0 && a > INT_MAX - x) // `a + x` would overflow
if (x < 0 && a < INT_MIN - x) // `a + x` would underflow

---

// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if (x < 0 && a > INT_MAX + x) // `a - x` would overflow
if (x > 0 && a < INT_MIN + x) // `a - x` would underflow

---

// For multiplication
#include <limits.h>

int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if (a == -1 && x == INT_MIN) // `a * x` can overflow
if (x == -1 && a == INT_MIN) // `a * x` (or `a / x`) can overflow
// general case
if (x != 0 && a > INT_MAX / x) // `a * x` would overflow
if (x != 0 && a < INT_MIN / x) // `a * x` would underflow

---

Für die Division (außer für die INT_MIN y -1 Sonderfall), gibt es keine Möglichkeit der Überschreitung INT_MIN ou INT_MAX .

Answer 2

Beginnend mit C23, der Standardkopfzeile <stdckdint.h> bietet die folgenden drei funktionsähnlichen Makros:

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

où type1 , type2 y type3 ein beliebiger Ganzzahlentyp sind. Diese Funktionen addieren, subtrahieren oder multiplizieren jeweils a und b mit beliebiger Genauigkeit und speichern das Ergebnis in *result . Wenn das Ergebnis nicht genau durch die folgende Formel dargestellt werden kann type1 gibt die Funktion true ("die Rechnung ist übergelaufen"). (Beliebige Genauigkeit ist eine Illusion; die Berechnungen sind sehr schnell, und fast alle seit den frühen 1990er Jahren verfügbare Hardware kann sie in nur ein oder zwei Anweisungen ausführen).

Das Beispiel von OP umschreiben:

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

c_test enthält in allen Fällen das Ergebnis der Multiplikation, das möglicherweise überlaufen ist.

Lange vor C23, GCC 5+ und Clang 3.8+ bieten Built-Ins, die auf die gleiche Weise funktionieren, mit der Ausnahme, dass der Ergebniszeiger als letzter statt als erster übergeben wird: __builtin_add_overflow , __builtin_sub_overflow y __builtin_mul_overflow . Diese funktionieren auch bei Typen kleiner als int .

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+ führte Arithmetic-Overflow-Builtins mit festen Typen ein, aber sie sind viel weniger flexibel, und Clang 3.8 ist schon seit langem verfügbar. Suchen Sie nach __builtin_umull_overflow wenn Sie diese trotz der neueren und bequemeren Alternative verwenden müssen.

Visual Studio 's cl.exe hat keine direkten Entsprechungen. Für vorzeichenlose Additionen und Subtraktionen, einschließlich <intrin.h> ermöglicht Ihnen die Verwendung von addcarry_uNN y subborrow_uNN (wobei NN die Anzahl der Bits ist, wie addcarry_u8 ou subborrow_u64 ). Ihre Unterschrift ist ein wenig stumpf:

unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);

c_in / b_in ist das Carry/Borrow-Flag am Eingang, und der Rückgabewert ist der Carry/Borrow am Ausgang. Es scheint keine Entsprechungen für Operationen mit Vorzeichen oder Multiplikationen zu geben.

Ansonsten ist Clang für Windows jetzt produktionsreif (gut genug für Chrome), also könnte das auch eine Option sein.

Answer 3

Dort es eine Möglichkeit, anhand der Positionen der höchstwertigen Ein-Bit-Bits in den Operanden und mit ein wenig binär-mathematischem Grundwissen festzustellen, ob bei einer Operation ein Überlauf zu erwarten ist.

Bei der Addition ergeben zwei beliebige Operanden (höchstens) ein Bit mehr als das höchste Ein-Bit des größten Operanden. Zum Beispiel:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

Bei der Multiplikation ergeben zwei beliebige Operanden (höchstens) die Summe der Bits der Operanden. Zum Beispiel:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

In ähnlicher Weise können Sie die maximale Größe des Ergebnisses von a an die Macht der b wie diese:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Ersetzen Sie natürlich die Anzahl der Bits durch Ihre Ziel-Ganzzahl).

Ich bin mir nicht sicher, wie man am schnellsten die Position des höchsten Bits in einer Zahl bestimmen kann, hier ist eine Brute-Force-Methode:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

Das ist zwar nicht perfekt, aber so können Sie sich ein gutes Bild davon machen, ob zwei Zahlen überlaufen könnten, bevor Sie die Operation durchführen. Ich weiß nicht, ob das schneller wäre als die Überprüfung des Ergebnisses auf die von Ihnen vorgeschlagene Weise, da die Schleife in der highestOneBitPosition Funktion, aber es könnte (vor allem, wenn Sie vorher wussten, wie viele Bits die Operanden enthielten).

Answer 4

Einige Compiler bieten Zugriff auf das Integer-Überlauf-Flag in der CPU, das Sie dann testen könnten, aber das ist nicht Standard.

Sie könnten auch auf die Möglichkeit eines Überlaufs testen, bevor Sie die Multiplikation durchführen:

if ( b > ULONG_MAX / a ) // a * b would overflow

Answer 5

Warnung: GCC kann eine Überlaufprüfung wegoptimieren, wenn er mit -O2 . Die Option -Wall gibt in einigen Fällen eine Warnung aus, z. B.

if (a + b < a) { /* Deal with overflow */ }

aber nicht in diesem Beispiel:

b = abs(a);
if (b < 0) { /* Deal with overflow */ }

Der einzige sichere Weg ist, auf einen Überlauf zu prüfen, bevor er auftritt, wie im Abschnitt CERT-Papier und das wäre unglaublich mühsam, wenn man es systematisch anwenden würde.

Kompilieren mit -fwrapv löst das Problem, schaltet aber einige Optimierungen aus.

Wir brauchen dringend eine bessere Lösung. Ich denke, der Compiler sollte standardmäßig eine Warnung ausgeben, wenn er eine Optimierung vornimmt, die darauf beruht, dass kein Überlauf auftritt. Die derzeitige Situation erlaubt es dem Compiler, eine Überlaufprüfung weg zu optimieren, was meiner Meinung nach inakzeptabel ist.