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

Der einfachste Weg ist die Umwandlung Ihrer unsigned long s in unsigned long long s, führen Sie die Multiplikation durch und vergleichen Sie das Ergebnis mit 0x100000000LL.

Sie werden wahrscheinlich feststellen, dass dies effizienter ist als die Division, wie Sie sie in Ihrem Beispiel durchgeführt haben.

Oh, und es wird sowohl in C als auch in C++ funktionieren (da Sie die Frage mit beiden getaggt haben).

---

Ich habe gerade einen Blick auf die glibc-Handbuch . Es gibt einen Hinweis auf eine Integer-Überlauffalle ( FPE_INTOVF_TRAP ) als Teil von SIGFPE . Das wäre ideal, abgesehen von den unangenehmen Stellen im Handbuch:

FPE_INTOVF_TRAP Integer-Überlauf (unmöglich in einem C-Programm, es sei denn, Sie aktivieren die Überlaufabfangung auf eine hardwarespezifische Weise).

Das ist wirklich ein bisschen schade.

Answer 2

Sie können von C/C++ aus nicht auf das Überlaufflag zugreifen.

Einige Compiler erlauben es, Trap-Befehle in den Code einzufügen. Bei GCC lautet die Option -ftrapv .

Die einzige portable und Compiler-unabhängige Maßnahme, die Sie ergreifen können, ist, selbst auf Überläufe zu prüfen. So wie Sie es in Ihrem Beispiel getan haben.

Allerdings, -ftrapv scheint auf x86 unter Verwendung des neuesten GCC nichts zu bewirken. Ich vermute, es ist ein Überbleibsel aus einer alten Version oder spezifisch für eine andere Architektur. Ich hatte erwartet, dass der Compiler nach jeder Addition einen INTO-Opcode einfügt. Leider tut er das nicht.

Answer 3

Bei ganzen Zahlen ohne Vorzeichen wird lediglich geprüft, ob das Ergebnis kleiner als eines der Argumente ist:

unsigned int r, a, b;
r = a + b;
if (r < a)
{
    // Overflow
}

Bei ganzen Zahlen mit Vorzeichen können Sie die Vorzeichen der Argumente und des Ergebnisses überprüfen.

Ganzzahlen mit unterschiedlichem Vorzeichen können nicht überlaufen, und Ganzzahlen mit gleichem Vorzeichen können nur überlaufen, wenn das Ergebnis ein anderes Vorzeichen hat:

signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // Overflow
}

Answer 4

Ich musste die gleiche Frage für Fließkommazahlen beantworten, bei denen Bitmaskierung und -verschiebung nicht vielversprechend sind. Der Ansatz, auf den ich mich geeinigt habe, funktioniert für vorzeichenbehaftete und vorzeichenlose, ganzzahlige und Fließkommazahlen. Er funktioniert auch dann, wenn es keinen größeren Datentyp gibt, auf den für Zwischenberechnungen umgestellt werden kann. Er ist nicht für alle diese Typen am effizientesten, aber da er für alle funktioniert, lohnt sich seine Anwendung.

Überlauftest mit Vorzeichen, Addition und Subtraktion:

1. Ermitteln Sie die Konstanten, die die größten und kleinsten möglichen Werte für den Typ darstellen, MAXVALUE und MINVALUE.

2. Berechnen und vergleichen Sie die Vorzeichen der Operanden.

   a. Wenn einer der beiden Werte Null ist, kann weder die Addition noch die Subtraktion einen Überlauf verursachen. Überspringen Sie die restlichen Tests.

   b. Wenn die Vorzeichen entgegengesetzt sind, dann kann die Addition nicht überlaufen. Überspringen Sie die restlichen Tests.

   c. Wenn die Vorzeichen gleich sind, dann kann die Subtraktion nicht überlaufen. Überspringen Sie die restlichen Tests.

3. Test auf positiven Überlauf von MAXVALUE.

   a. Wenn beide Vorzeichen positiv sind und MAXVALUE - A < B, dann wird die Addition überlaufen.

   b. Wenn das Vorzeichen von B negativ ist und MAXVALUE - A < -B, dann wird die Subtraktion überlaufen.

4. Test auf negativen Überlauf von MINVALUE.

   a. Wenn beide Vorzeichen negativ sind und MINVALUE - A > B, dann wird die Addition überlaufen.

   b. Wenn das Vorzeichen von A negativ ist und MINVALUE - A > B, dann wird die Subtraktion überlaufen.

5. Ansonsten kein Überlauf.

Überlauftest mit Vorzeichen, Multiplikation und Division:

1. Ermitteln Sie die Konstanten, die die größten und kleinsten möglichen Werte für den Typ darstellen, MAXVALUE und MINVALUE.

2. Berechne und vergleiche die Beträge (Absolutwerte) der Operanden mit Eins. (Im Folgenden wird davon ausgegangen, dass A und B diese Beträge sind, nicht die vorzeichenbehafteten Originale).

   a. Wenn einer der beiden Werte Null ist, kann die Multiplikation nicht überlaufen, und die Division ergibt Null oder Unendlich.

   b. Wenn einer der beiden Werte eins ist, können Multiplikation und Division nicht überlaufen.

   c. Wenn der Betrag des einen Operanden kleiner als eins und der des anderen größer als eins ist, kann die Multiplikation nicht überlaufen.

   d. Wenn die Beträge beide kleiner als eins sind, kann die Division nicht überlaufen.

3. Test auf positiven Überlauf von MAXVALUE.

   a. Wenn beide Operanden größer als eins sind und MAXVALUE / A < B, dann wird die Multiplikation überlaufen.

   b. Wenn B kleiner als eins ist und MAXVALUE * B < A, dann wird die Division überlaufen.

4. Ansonsten kein Überlauf.

Hinweis: Der minimale Überlauf von MINVALUE wird von 3 gehandhabt, da wir absolute Werte genommen haben. Wenn jedoch ABS(MINVALUE) > MAXVALUE, kommt es in seltenen Fällen zu falsch positiven Ergebnissen.

Die Tests für den Unterlauf sind ähnlich, beziehen sich aber auf EPSILON (die kleinste positive Zahl größer als Null).

Answer 5

Ein weiteres interessantes Instrument ist IOC: Ein Integer Overflow Checker für C/C++ .

Dies ist eine gepatchte Clang Compiler, der den Code während der Kompilierung überprüft.

Sie erhalten eine Ausgabe, die etwa so aussieht:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1