Wie erkenne ich einen vorzeichenlosen Ganzzahl-Multiplikationsüberlauf?

618

Ich habe ein Programm in C ++ geschrieben, um alle Lösungen von a b = c zu finden , wobei a , b und c alle Ziffern 0-9 genau einmal zusammen verwenden. Das Programm durchlief die Werte von a und b und führte jedes Mal eine Zählroutine für a , b und a b durch , um zu überprüfen, ob die Ziffernbedingung erfüllt war.

Es können jedoch falsche Lösungen erzeugt werden, wenn a b die ganzzahlige Grenze überschreitet. Am Ende habe ich dies mit folgendem Code überprüft:

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 über C oder C ++ darauf zugegriffen wird.


Beachten Sie, dass der signierte int Überlauf in C und C ++ ein undefiniertes Verhalten ist und Sie ihn daher erkennen müssen, ohne ihn tatsächlich zu verursachen. Informationen zum signierten int-Überlauf vor dem Hinzufügen finden Sie unter Erkennen des signierten Überlaufs in C / C ++ .

Chris Johnson
quelle
21
Informationen, die zu diesem Thema nützlich sein können: Kapitel 5 von "Sichere Codierung in C und C ++" von Seacord - http://www.informit.com/content/images/0321335724/samplechapter/seacord_ch05.pdf SafeInt-Klassen für C ++ - http : //blogs.msdn.com/david_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspx - http://www.codeplex.com/SafeInt IntSafe-Bibliothek für C: - [ blogs.msdn .com / michael_howard / archiv
Michael Burr
3
Die sichere Codierung von Seacord ist eine großartige Ressource, aber verwenden Sie keine IntegerLib. Siehe blog.regehr.org/archives/593 .
JWW
32
Die gcc-Compileroption -ftrapvbewirkt, dass bei einem (vorzeichenbehafteten) Ganzzahlüberlauf ein SIGABRT generiert wird. Siehe hier .
Nibot
1
Die Überlauffrage wird nicht beantwortet, aber eine andere Möglichkeit, das Problem zu lösen, besteht darin, eine BigNum-Bibliothek wie GMP zu verwenden, um sicherzustellen , dass Sie immer über genügend Präzision verfügen. Sie müssen sich keine Gedanken über einen Überlauf machen, wenn Sie im Voraus genügend Ziffern zuweisen.
Wrdieter
1
Die Informationen, die @HeadGeek in seiner Antwort gegeben hat, sind so ziemlich das, was ich auch sagen würde. Allerdings mit einem Zusatz. Die Art und Weise, wie Sie jetzt einen Überlauf für eine Multiplikation erkennen, ist wahrscheinlich die schnellste. Auf ARM können Sie, wie ich in der Antwort von HeadGeek kommentiert habe, die clzAnweisung oder die __clz(unsigned)Funktion verwenden, um den Rang der Zahl zu bestimmen (wobei das höchste Bit ist). Da ich nicht sicher bin, ob dies auf x86 oder x64 verfügbar ist, gehe ich davon aus, dass dies nicht der Fall ist, und sage, dass das Finden des höchstwertigen Bits im schlimmsten Fall log(sizeof(int)*8)Anweisungen erfordert.
nonsensickle

Antworten:

229

Ich sehe, dass Sie vorzeichenlose Ganzzahlen verwenden. Per Definition läuft in C (ich weiß nichts über C ++) die vorzeichenlose Arithmetik nicht über ... also, zumindest für C, ist Ihr Punkt umstritten :)

Bei vorzeichenbehafteten Ganzzahlen ist nach einem Überlauf ein undefiniertes Verhalten (UB) aufgetreten, und Ihr Programm kann alles tun (z. B. Tests nicht schlüssig machen). 

#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 vor dem Generieren des Überlaufs auf Überlauf testen . Die Methode kann auch mit vorzeichenlosen Ganzzahlen 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 (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

Bei der Division ( mit Ausnahme der INT_MINund -1Sonderfall), gibt es keine Möglichkeit , gehen über INT_MINoder INT_MAX.

pmg
quelle
97
Ganzzahlen ohne Vorzeichen laufen auch in C ++ nicht strikt über (ISO / IEC 14882: 2003 3.9.1.4). Meine Verwendung von 'Überlauf' in der Frage war die umgangssprachlichere Bedeutung, die das genau definierte Umschließen von vorzeichenlosen Typen einschließen sollte, da ich an vorzeichenlosen Ints interessiert war, die mathematisch positive ganze Zahlen darstellen, nicht positive ganze Zahlen mod 2 ^ 32 (oder 2 ^) 64). Die Unterscheidung zwischen Überlauf als Abweichung vom mathematischen unendlich großen Ganzzahlverhalten und Überlauf als undefiniertes Verhalten in der Sprache scheint selten explizit gemacht zu werden.
Chris Johnson
15
Dieser Test muss nicht sein x >= 0- x > 0wird ausreichen (wenn x == 0, dann x + akann er aus offensichtlichen Gründen nicht überlaufen).
Café
2
@pmg, gibt es ein unterstützendes Zitat aus dem Standard?
Pacerier
5
Ich mag diesen Ansatz ... Seien Sie jedoch vorsichtig: Die Multiplikationsüberlauferkennung setzt ein positives x voraus. Für x == 0 führt dies dazu, dass durch Null geteilt wird, und für negatives x wird immer fälschlicherweise ein Überlauf erkannt.
Franz D.
4
if ((a < INT_MIN / x))Test ist zu spät. if (x == -1) Zuerst wird ein Test benötigt.
chux
164

Es gibt eine Möglichkeit, anhand der Positionen der höchstwertigen Ein-Bits in den Operanden und einiger grundlegender binär-mathematischer Kenntnisse zu bestimmen, ob eine Operation wahrscheinlich überläuft.

Außerdem 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 aauf folgende Potenz schätzen b:

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 Ihre Ziel-Ganzzahl durch die Anzahl der Bits.)

Ich bin mir nicht sicher, wie ich am schnellsten die Position des höchsten Einzelbits 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;
}

Es ist nicht perfekt, aber das gibt Ihnen eine gute Vorstellung davon, ob zwei Zahlen überlaufen könnten, bevor Sie die Operation ausführen. Ich weiß nicht, ob es aufgrund der Schleife in der highestOneBitPositionFunktion schneller wäre, als das Ergebnis einfach so zu überprüfen, wie Sie es vorgeschlagen haben , aber es könnte sein (insbesondere, wenn Sie vorher wussten, wie viele Bits in den Operanden waren).

Head Geek
quelle
98
und natürlich können Sie highOneBitPosition in log umbenennen :)
Oliver Hallam
37
Ja, es ist die gleiche Operation wie log2, aber das wäre für jemanden ohne mathematischen Hintergrund nicht unbedingt so offensichtlich.
Head Geek
48
Unterschätzt dieser Algorithmus nicht die sicheren Antworten? 2 ^ 31 + 0 würde als unsicher erkennen, da höchsteOneBitPosition (2 ^ 31) = 32. (2 ^ 32 - 1) * 1 würde als unsicher erkennen, da 32 + 1> 32. 1 ^ 100 würde als unsicher seit 1 * 100 erkennen > 32.
Clahey
19
entsprechend Ihrem multiplication_is_safe 0x8000 * 0x10000würde Überlauf (Bitpositionen sind 16 + 17 = 33, was > 32 ist ), obwohl dies nicht 0x8000 * 0x10000 = 0x80000000der Fall ist, weil das offensichtlich immer noch in ein vorzeichenloses 32-Bit-Int passt. Dies ist nur eines von vielen Beispielen, für die dieser Code nicht funktioniert. 0x8000 * 0x10001, ...
Michi
13
@GT_mh: Dein Punkt? Wie gesagt, es ist nicht perfekt; es ist eine Regel-of-Daumen, der definitiv sagen, wenn etwas ist sicher, aber es gibt keinen Weg , um zu bestimmen , ob jede Berechnung , ohne dabei die volle Berechnung in Ordnung wäre. 0x8000 * 0x10000ist nach dieser Definition nicht "sicher", obwohl es sich als in Ordnung herausstellt.
Head Geek
147

Clang 3.4+ und GCC 5+ bieten geprüfte arithmetische Einbauten. Sie bieten eine sehr schnelle Lösung für dieses Problem, insbesondere im Vergleich zu Sicherheitsprüfungen bei Bittests.

Für das Beispiel in der Frage von OP würde es so funktionieren:

unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
    // Returned non-zero: there has been an overflow
}
else
{
    // Return zero: there hasn't been an overflow
}

In der Clang-Dokumentation wird nicht angegeben, ob c_testdas übergelaufene Ergebnis enthalten ist, wenn ein Überlauf aufgetreten ist. In der GCC-Dokumentation wird dies jedoch angegeben. Angesichts der Tatsache, dass diese beiden gerne __builtinkompatibel sind, kann man davon ausgehen, dass Clang auch so funktioniert.

Es gibt einen __builtinfür jede Rechenoperation , die überlaufen kann (Addition, Subtraktion, Multiplikation), mit und ohne Vorzeichen Varianten für int Größen lange Größen und lange lange Größen. Die Syntax für den Namen lautet __builtin_[us](operation)(l?l?)_overflow:

  • ufür nicht signiert oder sfür signiert ;
  • Betrieb eines von add, suboder mul;
  • kein lSuffix bedeutet, dass die Operanden ints sind; man lmeint long; zwei ls bedeuten long long.

Für eine überprüfte vorzeichenbehaftete lange Ganzzahladdition wäre dies also der Fall __builtin_saddl_overflow. Die vollständige Liste finden Sie auf der Clang-Dokumentationsseite .

GCC 5+ und Clang 3.8+ bieten zusätzlich generic builtins , dass die Arbeit ohne die Art des Wertes festgelegt wird : __builtin_add_overflow, __builtin_sub_overflowund __builtin_mul_overflow. Diese funktionieren auch bei Typen, die kleiner als sind int.

Die Einbauten senken sich auf das Beste für die Plattform. Auf x86 überprüfen sie die Übertrags-, Überlauf- und Vorzeichenflags.

Die cl.exe von Visual Studio hat keine direkten Entsprechungen. Für vorzeichenlose Additionen und Subtraktionen, einschließlich <intrin.h>, können Sie addcarry_uNNund verwenden subborrow_uNN(wobei NN die Anzahl der Bits ist, wie addcarry_u8oder subborrow_u64). Ihre Unterschrift ist etwas 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_inist das Carry / Borrow-Flag bei der Eingabe und der Rückgabewert ist das Carry / Borrow bei der Ausgabe. Es scheint keine Äquivalente für vorzeichenbehaftete Operationen oder Multiplikationen zu geben.

Andernfalls ist Clang für Windows jetzt produktionsbereit (gut genug für Chrome), sodass dies ebenfalls eine Option sein könnte.

zneak
quelle
__builtin_sub_overflowist definitiv nicht in Clang 3.4.
Richard Cook
2
@RichardCook, es hat einige Zeit gedauert, aber Clang hat die generischen Buildins ab Version 3.9.
Zneak
@tambre, ich glaube nicht, dass es gibt.
Zneak
4
Laut den Dokumenten sollten __builtin_add_overflowund Freunde bereits auf Clang 3.8 verfügbar sein.
Lekensteyn
2
Vielen Dank. Das funktioniert super. Irgendeine Idee, was die entsprechende Funktion für Visual C ++ ist? Kann sie nicht finden.
Mudit Jain
53

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

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

if ( b > ULONG_MAX / a ) // a * b would overflow
Robert Gamble
quelle
11
... oder benutze numeric_limits <TYPE> :: max ()
Jonas Gulle
20
Vergessen Sie dann nicht, a = 0 zu behandeln - Teilungspausen.
Thelema
16
@Thelema: "Vergiss nicht, mit a = 0 umzugehen" - und INT_MIN / -1.
JWW
1
Was wäre wenn b == ULONG_MAX / a? Dann kann es noch passen, vorausgesetzt, es ateilt sich ULONG_MAXohne Rest.
das Schwein
Komisch, dass eine Multiplikation in Bezug auf die Leistung im Vergleich zu einer Division ziemlich schnell ist und Sie für jede Multiplikation eine Division hinzufügen. Das klingt nicht nach einer Lösung.
DrumM
40

Warnung: GCC kann eine Überlaufprüfung beim Kompilieren mit optimieren -O2. Die Option -Wallgibt Ihnen in einigen Fällen eine Warnung wie

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

aber nicht in diesem Beispiel:

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

Der einzig sichere Weg besteht darin, vor dem Auftreten auf Überlauf zu prüfen, wie im CERT-Dokument beschrieben . Eine systematische Verwendung wäre unglaublich mühsam.

Das Kompilieren mit -fwrapvlöst das Problem, deaktiviert jedoch einige Optimierungen.

Wir brauchen dringend eine bessere Lösung. Ich denke, der Compiler sollte standardmäßig eine Warnung ausgeben, wenn eine Optimierung vorgenommen wird, die darauf beruht, dass kein Überlauf auftritt. Die gegenwärtige Situation ermöglicht es dem Compiler, eine Überlaufprüfung zu optimieren, was meiner Meinung nach nicht akzeptabel ist.

Ein Nebel
quelle
8
Beachten Sie, dass Compiler dies nur mit vorzeichenbehafteten Ganzzahltypen tun dürfen . Der Überlauf ist für die vorzeichenlosen Ganzzahltypen vollständig definiert. Trotzdem ist es eine ziemlich gefährliche Falle!
SamB
1
"Ich denke, der Compiler sollte standardmäßig eine Warnung ausgeben, wenn eine Optimierung vorgenommen wird, die darauf beruht, dass kein Überlauf auftritt." - for(int k = 0; k < 5; k++) {...}sollte also eine Warnung ausgelöst werden?
user253751
2
@immibis: Warum sollte es? Die Werte von kkönnen zur Kompilierungszeit leicht bestimmt werden. Der Compiler muss keine Annahmen treffen.
MikeMB
2
@immibis: Um das Obige zu zitieren: "Ich denke, der Compiler sollte standardmäßig eine Warnung ausgeben, wenn eine Optimierung vorgenommen wird , die darauf beruht, dass kein Überlauf auftritt."
MikeMB
1
@MikeMB Die Optimierung, bei der der Compiler nicht prüft, ob sie nkleiner als 32 ist, bevor ein Verschiebungsbefehl ausgegeben wird, der nur die unteren 5 Bits von n? Verwendet .
user253751
30

Clang unterstützt jetzt dynamische Überlaufprüfungen für vorzeichenbehaftete und vorzeichenlose Ganzzahlen. Siehe den Schalter -fsanitize = integer . Derzeit ist es der einzige C ++ - Compiler mit vollständig unterstützter dynamischer Überlaufprüfung für Debugzwecke.

ZAB
quelle
25

Ich sehe, dass viele Leute die Frage nach dem Überlauf beantwortet haben, aber ich wollte sein ursprüngliches Problem ansprechen. Er sagte, das Problem sei, ein b = c zu finden, so dass alle Ziffern ohne Wiederholung verwendet werden. Ok, das hat er in diesem Beitrag nicht gefragt, aber ich denke immer noch, dass es notwendig war, die Obergrenze des Problems zu untersuchen und zu dem Schluss zu kommen, dass er niemals einen Überlauf berechnen oder erkennen müsste (Hinweis: Ich bin nicht kompetent In Mathe habe ich das Schritt für Schritt gemacht, aber das Endergebnis war so einfach, dass dies eine einfache Formel haben könnte.

Der Hauptpunkt ist, dass die Obergrenze, die das Problem für a, b oder c erfordert, 98,765,432 beträgt. Beginnen Sie mit der Aufteilung des Problems in triviale und nicht triviale Teile:

  • x 0 == 1 (alle Permutationen von 9, 8, 7, 6, 5, 4, 3, 2 sind Lösungen)
  • x 1 == x (keine Lösung möglich)
  • 0 b == 0 (keine Lösung möglich)
  • 1 b == 1 (keine Lösung möglich)
  • a b , a> 1, b> 1 (nicht trivial)

Jetzt müssen wir nur noch zeigen, dass keine andere Lösung möglich ist und nur die Permutationen gültig sind (und dann ist der Code zum Drucken trivial). Wir gehen zurück zur Obergrenze. Tatsächlich ist die Obergrenze c ≤ 98,765,432. Es ist die Obergrenze, weil es die größte Zahl mit 8 Ziffern ist (10 Ziffern insgesamt minus 1 für jedes a und b). Diese Obergrenze gilt nur für c, da die Grenzen für a und b aufgrund des exponentiellen Wachstums, wie wir berechnen können, viel niedriger sein müssen und b von 2 bis zur Obergrenze variieren:

    9938.08^2 == 98765432
    462.241^3 == 98765432
    99.6899^4 == 98765432
    39.7119^5 == 98765432
    21.4998^6 == 98765432
    13.8703^7 == 98765432
    9.98448^8 == 98765432
    7.73196^9 == 98765432
    6.30174^10 == 98765432
    5.33068^11 == 98765432
    4.63679^12 == 98765432
    4.12069^13 == 98765432
    3.72429^14 == 98765432
    3.41172^15 == 98765432
    3.15982^16 == 98765432
    2.95305^17 == 98765432
    2.78064^18 == 98765432
    2.63493^19 == 98765432
    2.51033^20 == 98765432
    2.40268^21 == 98765432
    2.30883^22 == 98765432
    2.22634^23 == 98765432
    2.15332^24 == 98765432
    2.08826^25 == 98765432
    2.02995^26 == 98765432
    1.97741^27 == 98765432

Beachten Sie zum Beispiel die letzte Zeile: Es heißt, dass 1,97 ^ 27 ~ 98M. Zum Beispiel 1 ^ 27 == 1 und 2 ^ 27 == 134.217.728 und das ist keine Lösung, da es 9 Ziffern hat (2> 1,97, also ist es tatsächlich größer als das, was getestet werden sollte). Wie zu sehen ist, sind die zum Testen von a und b verfügbaren Kombinationen sehr klein. Für b == 14 müssen wir 2 und 3 versuchen. Für b == 3 beginnen wir bei 2 und enden bei 462. Alle Ergebnisse werden mit weniger als ~ 98M bewertet.

Testen Sie jetzt einfach alle oben genannten Kombinationen und suchen Sie nach Kombinationen, die keine Ziffern wiederholen:

    ['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
    ['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
    ['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
    ['1', '2', '3', '5', '8'] 8^3 = 512
    ['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
    ['1', '2', '4', '6'] 4^2 = 16
    ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
    ['1', '2', '4', '6'] 2^4 = 16
    ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
    ['1', '2', '8', '9'] 9^2 = 81
    ['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
    ['1', '3', '4', '8'] 3^4 = 81
    ['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
    ['2', '3', '6', '7', '9'] 3^6 = 729
    ['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
    ['2', '3', '8'] 2^3 = 8
    ['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
    ['2', '3', '9'] 3^2 = 9
    ['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
    ['2', '4', '6', '8'] 8^2 = 64
    ['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
    ['2', '4', '7', '9'] 7^2 = 49
    ['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)

Keiner von ihnen entspricht dem Problem (was auch am Fehlen von '0', '1', ..., '9' zu erkennen ist).

Der Beispielcode, der es löst, folgt. Beachten Sie auch, dass dies in Python geschrieben ist, nicht weil es Ganzzahlen mit beliebiger Genauigkeit benötigt (der Code berechnet nichts Größeres als 98 Millionen), sondern weil wir herausgefunden haben, dass die Anzahl der Tests so gering ist, dass wir eine Hochsprache verwenden sollten Nutzen Sie die integrierten Container und Bibliotheken (beachten Sie auch: Der Code hat 28 Zeilen).

    import math

    m = 98765432
    l = []
    for i in xrange(2, 98765432):
        inv = 1.0/i
        r = m**inv
        if (r < 2.0): break
        top = int(math.floor(r))
        assert(top <= m)

        for j in xrange(2, top+1):
            s = str(i) + str(j) + str(j**i)
            l.append((sorted(s), i, j, j**i))
            assert(j**i <= m)

    l.sort()
    for s, i, j, ji in l:
        assert(ji <= m)
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d' % (s, i, j, ji)

        # Try with non significant zero somewhere
        s = ['0'] + s
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)
hdante
quelle
1
Warum verwenden Sie nicht 9.876.543.210 als Obergrenze?
Tom Roggero
3
Weil für die linke Seite der Gleichung 2 Ziffern verwendet werden müssen.
hdante
2
Nicht, dass es einen Unterschied macht, aber die Obergrenze kann tatsächlich als 98765410 angenommen werden, da Sie angegeben haben, dass die Werte auf der LHS> 1 sind
Paul Childs
24

Hier ist eine "nicht tragbare" Lösung für die Frage. Die Intel x86- und x64-CPUs haben das sogenannte EFLAGS-Register , das nach jeder ganzzahligen arithmetischen Operation vom Prozessor ausgefüllt wird. Ich werde hier eine detaillierte Beschreibung überspringen. Die relevanten Flags sind das "Overflow" -Flag (Maske 0x800) und das "Carry" -Flag (Maske 0x1). Um sie richtig zu interpretieren, sollte man überlegen, ob die Operanden vom Typ mit oder ohne Vorzeichen sind.

Hier ist eine praktische Möglichkeit, die Flags von C / C ++ zu überprüfen. Der folgende Code funktioniert unter Visual Studio 2005 oder neuer (sowohl 32- als auch 64-Bit) sowie unter GNU C / C ++ 64-Bit.

#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif

inline size_t query_intel_x86_eflags(const size_t query_bit_mask)
{
    #if defined( _MSC_VER )

        return __readeflags() & query_bit_mask;

    #elif defined( __GNUC__ )
        // This code will work only on 64-bit GNU-C machines.
        // Tested and does NOT work with Intel C++ 10.1!
        size_t eflags;
        __asm__ __volatile__(
            "pushfq \n\t"
            "pop %%rax\n\t"
            "movq %%rax, %0\n\t"
            :"=r"(eflags)
            :
            :"%rax"
            );
        return eflags & query_bit_mask;

    #else

        #pragma message("No inline assembly will work with this compiler!")
            return 0;
    #endif
}

int main(int argc, char **argv)
{
    int x = 1000000000;
    int y = 20000;
    int z = x * y;
    int f = query_intel_x86_eflags(0x801);
    printf("%X\n", f);
}

Wenn die Operanden ohne Überlauf multipliziert würden, würden Sie einen Rückgabewert von 0 erhalten query_intel_eflags(0x801), dh weder die Übertrags- noch die Überlaufflags werden gesetzt. In dem bereitgestellten Beispielcode von main () tritt ein Überlauf auf und die beiden Flags werden auf 1 gesetzt. Diese Überprüfung impliziert keine weiteren Berechnungen, daher sollte sie recht schnell sein.

Engel Sinigersky
quelle
21

Wenn Sie einen Datentyp haben, der größer ist als der, den Sie testen möchten (sagen wir, Sie führen eine 32-Bit-Addition durch und Sie haben einen 64-Bit-Typ), wird dadurch erkannt, ob ein Überlauf aufgetreten ist. Mein Beispiel ist ein 8-Bit-Add. Aber es kann vergrößert werden.

uint8_t x, y;    /* Give these values */
const uint16_t data16    = x + y;
const bool carry        = (data16 > 0xFF);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

Es basiert auf den auf dieser Seite erläuterten Konzepten: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

Für ein 32-Bit-Beispiel 0xFFwird 0xFFFFFFFFund 0x80wird 0x80000000und wird schließlich uint16_tein uint64_t.

HINWEIS : Dadurch werden Überläufe bei der Addition / Subtraktion von Ganzzahlen abgefangen, und mir wurde klar, dass Ihre Frage eine Multiplikation beinhaltet. In diesem Fall ist die Teilung wahrscheinlich der beste Ansatz. Auf diese Weise stellen callocImplementierungen normalerweise sicher, dass die Parameter nicht überlaufen, wenn sie multipliziert werden, um die endgültige Größe zu erhalten.

Evan Teran
quelle
Die Verbindung ist unterbrochen: HTTP 403: Verboten
Peter Mortensen
18

Am einfachsten ist es, Ihr unsigned longs in unsigned long longs umzuwandeln , Ihre Multiplikation durchzuführen und das Ergebnis mit 0x100000000LL zu vergleichen.

Sie werden wahrscheinlich feststellen, dass dies effizienter ist als die Aufteilung, wie Sie es in Ihrem Beispiel getan haben.

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


Ich habe mir gerade das glibc-Handbuch angesehen . Es wird eine ganzzahlige Überlauffalle ( FPE_INTOVF_TRAP) als Teil von erwähnt SIGFPE. Das wäre ideal, abgesehen von den fiesen Stellen im Handbuch:

FPE_INTOVF_TRAP Ganzzahliger Überlauf (in einem C-Programm nur möglich, wenn Sie das Überlauf-Trapping hardwarespezifisch aktivieren).

Ein bisschen schade wirklich.

Andrew Edgecombe
quelle
4
Heh ... was ich nicht gesagt habe war, dass ich diese Frage stelle, um ein Programm zur Lösung eines Problems mit größeren Zahlen vorzubereiten, in dem ich bereits long long int verwende. Da long long int (angeblich) nicht im C ++ - Standard enthalten ist, habe ich mich an die 32-Bit-Version gehalten, um Verwirrung zu vermeiden.
Chris Johnson
Ich würde empfehlen, zu verwenden, ULONG_MAXwas einfacher zu tippen und portabler ist als Hardcodierung 0x100000000.
jw013
24
Dies funktioniert nicht, wenn longund long longhaben dieselbe Größe (z. B. bei vielen 64-Bit-Compilern).
Interjay
Sich auf Signale zu verlassen, um über Überläufe zu informieren, wäre sowieso sehr langsam.
SamB
@SamB Nur wenn Überläufe zu erwarten waren.
user253751
17

Hier ist eine sehr schnelle Methode, um einen Überlauf für zumindest Additionen zu erkennen, was zu einem Vorsprung für Multiplikation, Division und Potenz führen kann.

Die Idee ist, dass Sie genau das tun können, weil der Prozessor den Wert einfach auf Null zurücksetzen lässt und C / C ++ von einem bestimmten Prozessor abstrahiert werden soll:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

Dies stellt sicher, dass ein Überlauf nicht fälschlicherweise erkannt wird, wenn ein Operand Null ist und einer nicht. Er ist erheblich schneller als viele zuvor vorgeschlagene NOT / XOR / AND / Test-Operationen.

Wie bereits erwähnt, ist dieser Ansatz zwar besser als andere ausgefeiltere Methoden, aber dennoch optimierbar. Das Folgende ist eine Überarbeitung des ursprünglichen Codes, der die Optimierung enthält:

uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work

Eine effizientere und kostengünstigere Methode zum Erkennen eines Multiplikationsüberlaufs ist:

uint32_t x, y;
const bool overflow = (x >> 16U) * (y >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

Dies führt entweder zu UINT32_MAX beim Überlauf oder zum Ergebnis der Multiplikation. In diesem Fall ist es streng undefiniert, die Multiplikation für vorzeichenbehaftete Ganzzahlen fortzusetzen.

DX-MON
quelle
Ich bin aufgrund der Berechnungstheorie nicht einverstanden. Beachten Sie Folgendes: y> x, Wert läuft über, y ist nur größer als x, da das Vorzeichenbit gesetzt ist (1 + 255, z. B. für vorzeichenlose Zeichen). Der Testwert und x würden sich ergeben in overflow = false - daher die Verwendung von logischen oder um dieses fehlerhafte Verhalten zu verhindern ..
DX-MON
Der Test funktioniert für die von Ihnen angegebenen Zahlen (x: = 1, y: = 255, size = uint8_t): Der Wert ist 0 (1 + 255) und 0 <1 ist wahr. Es funktioniert in der Tat für jedes Zahlenpaar.
Gunther Piez
Hmm, du machst einen guten Punkt. Ich bleibe immer noch auf der Seite der Sicherheit mit dem oder Trick, obwohl jeder gute Compiler den Anbieter optimieren würde, sind Sie in der Tat für alle Eingaben korrekt, einschließlich nicht überlaufender Zahlen wie "0 + 4", bei denen das Ergebnis nicht überlaufen würde.
DX-MON
4
Wenn es einen Überlauf gibt, als x+y>=256und value=x+y-256. Weil y<256immer wahr gilt, ist (y-256) negativ und so value < xist es immer wahr. Der Beweis für den nicht überfüllten Fall ist ziemlich ähnlich.
Gunther Piez
2
@ DX-MON: Ihre erste Methode ist erforderlich, wenn Sie auch ein Übertragsbit aus einem vorherigen Add haben. uint32_t x[N], y[N], z[N], carry=0; for (int i = 0; i < N; i++) { z[i] = x[i] + y[i] + carry; carry = z[i] < (x[i] | y[i]); }Wenn Sie ordie Werte nicht eingeben, können Sie nicht zwischen einem Operanden und dem Übertragsbit Null und einem Operanden 0xffffffffund dem Übertragsbit Eins unterscheiden.
Matt
14

Sie können nicht über C / C ++ auf das Überlauf-Flag zugreifen.

Bei einigen Compilern können Sie Trap-Anweisungen in den Code einfügen. Auf GCC ist die Option -ftrapv.

Das einzige tragbare und vom Compiler unabhängige Element, das Sie tun können, ist, selbst nach Überläufen zu suchen. Genau wie in Ihrem Beispiel.

Allerdings -ftrapvscheint nichts auf x86 zu tun , um die neuesten GCC. Ich denke, es ist ein Überbleibsel einer alten Version oder spezifisch für eine andere Architektur. Ich hatte erwartet, dass der Compiler nach jedem Hinzufügen einen INTO-Opcode einfügt. Leider macht es das nicht.

Nils Pipenbrinck
quelle
Vielleicht variiert es: -ftrapv scheint mit GCC 4.3.4 auf einer Cygwin-Box gut zu funktionieren. Es gibt ein Beispiel unter stackoverflow.com/questions/5005379/…
Nate Kohl
3
Sie haben beide recht. -ftrapv erledigen den Job, aber nur für vorzeichenbehaftete Ganzzahlen
ZAB
14

Überprüfen Sie bei vorzeichenlosen Ganzzahlen einfach, ob das Ergebnis kleiner als eines der Argumente ist:

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

Bei vorzeichenbehafteten Ganzzahlen können Sie die Vorzeichen der Argumente und des Ergebnisses überprüfen.

Ganzzahlen mit unterschiedlichen Vorzeichen können nicht überlaufen, und Ganzzahlen mit demselben 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
}
Peter Mortensen
quelle
Nun, die erste Methode würde auch für vorzeichenbehaftete Ganzzahlen funktionieren, nicht wahr? char result = (char)127 + (char)3;wäre -126; kleiner als beide Operanden.
Primfaktor
1
Oh ich verstehe, das Problem ist die Tatsache, dass es für signierte Typen undefiniert ist.
Primfaktor
27
-1 Überlauf von vorzeichenbehafteten Zahlen führt zu undefiniertem Verhalten (daher ist der Test zu spät, um tatsächlich nützlich zu sein).
Voo
1
@primfaktor es funktioniert nicht für signiertes int: char ((- 127) + (-17)) = 112. Für signiertes int müssen Sie das Vorzeichenbit der Argumente und des Ergebnisses
überprüfen
3
Wie bereits erwähnt, funktioniert die Lösung für vorzeichenbehaftete Ganzzahlen aufgrund des undefinierten Verhaltens von a + b im Falle eines Überlaufs nicht. Die Überprüfung auf Überlauf mit vorzeichenbehafteter Ganzzahl muss vor der Operation erfolgen.
Marwan Burelle
11

Ich musste dieselbe Frage für Gleitkommazahlen beantworten, bei denen Bitmaskierung und -verschiebung nicht vielversprechend aussehen. Der Ansatz, für den ich mich entschieden habe, funktioniert für vorzeichenbehaftete und vorzeichenlose Ganzzahl- und Gleitkommazahlen. Dies funktioniert auch dann, wenn kein größerer Datentyp für Zwischenberechnungen heraufgestuft werden muss. Es ist nicht das effizienteste für alle diese Typen, aber da es für alle funktioniert, lohnt es sich, es zu verwenden.

Signierter Überlauftest, Addition und Subtraktion:

  1. Erhalten Sie die Konstanten, die die größtmöglichen und kleinstmöglichen Werte für den Typ MAXVALUE und MINVALUE darstellen.

  2. Berechnen und vergleichen Sie die Vorzeichen der Operanden.

    ein. Wenn einer der Werte Null ist, kann weder Addition noch Subtraktion überlaufen. Überspringen Sie die verbleibenden Tests.

    b. Wenn die Vorzeichen entgegengesetzt sind, kann die Zugabe nicht überlaufen. Überspringen Sie die verbleibenden Tests.

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

  3. Auf positiven Überlauf von MAXVALUE prüfen.

    ein. Wenn beide Vorzeichen positiv sind und MAXVALUE - A <B, läuft die Addition über.

    b. Wenn das Vorzeichen von B negativ und MAXVALUE - A <-B ist, läuft die Subtraktion über.

  4. Auf negativen Überlauf von MINVALUE prüfen.

    ein. Wenn beide Vorzeichen negativ und MINVALUE - A> B sind, läuft die Addition über.

    b. Wenn das Vorzeichen von A negativ ist und MINVALUE - A> B, läuft die Subtraktion über.

  5. Ansonsten kein Überlauf.

Signierter Überlauftest, Multiplikation und Division:

  1. Erhalten Sie die Konstanten, die die größtmöglichen und kleinstmöglichen Werte für den Typ MAXVALUE und MINVALUE darstellen.

  2. Berechnen und vergleichen Sie die Größen (Absolutwerte) der Operanden mit eins. (Angenommen, A und B sind diese Größen, nicht die signierten Originale.)

    ein. Wenn einer der Werte Null ist, kann die Multiplikation nicht überlaufen, und die Division ergibt Null oder eine Unendlichkeit.

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

    c. Wenn die Größe eines Operanden unter dem einen und des anderen größer als eins ist, kann die Multiplikation nicht überlaufen.

    d. Wenn die Größen beide kleiner als eins sind, kann die Division nicht überlaufen.

  3. Auf positiven Überlauf von MAXVALUE prüfen.

    ein. Wenn beide Operanden größer als eins und MAXVALUE / A <B sind, läuft die Multiplikation über.

    b. Wenn B kleiner als eins ist und MAXVALUE * B <A ist, läuft die Division über.

  4. Ansonsten kein Überlauf.

Hinweis: Der minimale Überlauf von MINVALUE wird von 3 behandelt, da wir absolute Werte verwendet haben. Wenn jedoch ABS (MINVALUE)> MAXVALUE ist, haben wir einige seltene Fehlalarme.

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

Paul Chernoch
quelle
1
Zumindest auf POSIX-Systemen kann das SIGFPE-Signal für Gleitkomma-Unter- / Überläufe aktiviert werden.
Chris Johnson
Während die Konvertierung in Gleitkomma und zurück funktioniert, ist sie (nach meinen Tests auf einem 32-Bit-Computer) viel langsamer als die anderen Lösungen.
JanKanis
Ein Prüfer hat einen fehlenden Fall für Subtraktionsteil 2 festgestellt. Ich stimme zu, dass 0 - MINVALUE überlaufen würde. Daher sollten Tests für diesen Fall hinzugefügt werden.
Paul Chernoch
<pedantic> Ganzzahlen laufen nicht unter (= werden zu nahe an Null, um mit irgendeiner Genauigkeit dargestellt zu werden). 1.0e-200 / 1.0e200wäre ein Beispiel für einen tatsächlichen Unterlauf, vorausgesetzt, IEEE verdoppelt sich. Der korrekte Begriff hier ist stattdessen negativer Überlauf. </ Pedantic>
Arne Vogel
Um genau zu sein, liegt der Grund dafür, dass Ganzzahlen nicht als Unterlauf angesehen werden, in einem definierten Kürzungsverhalten, z. B. 1/INT_MAXkönnte dies als Unterlauf angesehen werden, aber die Sprache schreibt einfach eine Kürzung auf Null vor.
Arne Vogel
8

CERT hat einen neuen Ansatz zum Erkennen und Melden eines vorzeichenbehafteten Ganzzahlüberlaufs, eines vorzeichenlosen Ganzzahlumbruchs und einer Ganzzahlkürzung unter Verwendung des Ganzzahlmodells "als ob" mit unendlichem Bereich (AIR) entwickelt. CERT hat einen technischen Bericht veröffentlicht , der das Modell beschreibt, und einen funktionierenden Prototyp basierend auf GCC 4.4.0 und GCC 4.5.0 erstellt.

Das AIR-Ganzzahlmodell erzeugt entweder einen Wert, der einem Wert entspricht, der unter Verwendung von Ganzzahlen mit unendlichem Bereich erhalten worden wäre, oder führt zu einer Verletzung der Laufzeitbeschränkung. Im Gegensatz zu früheren Ganzzahlmodellen erfordern AIR-Ganzzahlen keine präzisen Traps und unterbrechen oder hemmen folglich die meisten vorhandenen Optimierungen nicht.

Robert C. Seacord
quelle
Ich habe unter dem Link nichts Nützliches gesehen, aber das klingt nach einem Modell, für das ich mich lange eingesetzt habe. Es unterstützt die überwiegende Mehrheit nützlicher Optimierungen und nützliche semantische Garantien, die die meisten Implementierungen im Wesentlichen kostenlos bereitstellen können. Wenn der Code weiß, dass die Eingaben in eine Funktion in allen Fällen gültig sind, in denen die Ausgabe von Bedeutung ist , aber nicht im Voraus weiß, ob die Ausgabe von Bedeutung ist, kann es vorkommen, dass Überläufe auftreten, wenn sie nichts beeinflussen einfacher und effizienter, als sie um jeden Preis verhindern zu müssen.
Supercat
8

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

Dies ist ein gepatchter Clang- Compiler, der dem Code zur Kompilierungszeit Überprüfungen hinzufügt.

Die Ausgabe sieht folgendermaßen aus:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
Willem Hengeveld
quelle
1
Dieser Patch wird jetzt zusammengeführt, um die Codebasis unter anderen Desinfektionsmitteln zu klirren. Siehe meine Antwort.
ZAB
7

Eine andere Variante einer Lösung, die Assemblersprache verwendet, ist ein externes Verfahren. Dieses Beispiel für die vorzeichenlose Ganzzahlmultiplikation mit g ++ und fasm unter Linux x64.

Diese Prozedur multipliziert zwei vorzeichenlose Ganzzahlargumente (32 Bit) (gemäß Spezifikation für amd64 (Abschnitt 3.2.3 Parameterübergabe ).

Wenn die Klasse INTEGER ist, wird das nächste verfügbare Register der Sequenz% rdi,% rsi,% rdx,% rcx,% r8 und% r9 verwendet

(edi und esi registrieren sich in meinem Code)) und gibt das Ergebnis oder 0 zurück, wenn ein Überlauf aufgetreten ist.

format ELF64

section '.text' executable

public u_mul

u_mul:
  MOV eax, edi
  mul esi
  jnc u_mul_ret
  xor eax, eax
u_mul_ret:
ret

Prüfung:

extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);

int main() {
    printf("%u\n", u_mul(4000000000,2)); // 0
    printf("%u\n", u_mul(UINT_MAX/2,2)); // OK
    return 0;
}

Verknüpfen Sie das Programm mit der asm-Objektdatei. In meinem Fall fügen Sie es in Qt CreatorLIBS einer .pro-Datei hinzu.

Bartolo-Otrit
quelle
5

Berechnen Sie die Ergebnisse mit Doppel. Sie haben 15 signifikante Ziffern. Ihre Anforderung hat eine harte Obergrenze für c von 10 8  - sie kann höchstens 8 Stellen haben. Daher ist das Ergebnis präzise, ​​wenn es sich in Reichweite befindet, und es läuft sonst nicht über.

MSalters
quelle
5

Probieren Sie dieses Makro aus, um das Überlaufbit von 32-Bit-Maschinen zu testen (angepasst an die Lösung von Angel Sinigersky).

#define overflowflag(isOverflow){   \
size_t eflags;                      \
asm ("pushfl ;"                     \
     "pop %%eax"                    \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

Ich habe es als Makro definiert, weil sonst das Überlaufbit überschrieben worden wäre.

Nachfolgend finden Sie eine kleine Anwendung mit dem obigen Codesegment:

#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif

using namespace std;

#define detectOverflow(isOverflow){     \
size_t eflags;                      \
asm ("pushfl ;"                     \
    "pop %%eax"                     \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

int main(int argc, char **argv) {

    bool endTest = false;
    bool isOverflow;

    do {
        cout << "Enter two intergers" << endl;
        int x = 0;
        int y = 0;
        cin.clear();
        cin >> x >> y;
        int z = x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow occured\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        z = x * x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow ocurred\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;

        char c = 0;

        do {
            c = getchar();
        } while ((c == '\n') && (c != EOF));

        if (c == 'y' || c == 'Y') {
            endTest = true;
        }

        do {
            c = getchar();
        } while ((c != '\n') && (c != EOF));

    } while (!endTest);
}
Markus Demarmels
quelle
4
Nicht alle 32-Bit-Computer sind Intel x86-kompatibel, und nicht alle Compiler unterstützen die Gnu-Assembly-Syntax (ich finde es lustig, dass Sie Code veröffentlichen, der testet, _MSC_VERobwohl MS-Kompilierungen den Code alle ablehnen).
Ben Voigt
2

Das Abfangen von Integer-Überläufen in C weist auf eine Lösung hin, die allgemeiner ist als die von CERT diskutierte (sie ist allgemeiner in Bezug auf behandelte Typen), selbst wenn einige GCC-Erweiterungen erforderlich sind (ich weiß nicht, wie weit sie unterstützt werden).

Blaisorblade
quelle
2

Sie können nicht über C / C ++ auf das Überlauf-Flag zugreifen.

Dem stimme ich nicht zu. Sie können eine Inline-Assemblersprache schreiben und eine joAnweisung (Sprungüberlauf) verwenden, vorausgesetzt, Sie befinden sich auf x86, um den Überlauf abzufangen. Natürlich wäre Ihr Code nicht mehr auf andere Architekturen portierbar.

Schau dir an info asund info gcc.

Tarski
quelle
8
Inline Assembler ist keine C / C ++ - Funktion und plattformunabhängig. Auf x86 können Sie die Anweisung into anstelle von Zweigen verwenden.
Nils Pipenbrinck
0

Um die Antwort von Head Geek zu erweitern, gibt es einen schnelleren Weg, dies zu tun addition_is_safe.

bool addition_is_safe(unsigned int a, unsigned int b)
{
    unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
    L_Mask >>= 1;
    L_Mask = ~L_Mask;

    a &= L_Mask;
    b &= L_Mask;

    return ( a == 0 || b == 0 );
}

Dies verwendet eine sichere Maschinenarchitektur, da vorzeichenlose 64-Bit- und 32-Bit-Ganzzahlen weiterhin einwandfrei funktionieren. Grundsätzlich erstelle ich eine Maske, die alle bis auf das höchstwertige Bit ausblendet. Dann maskiere ich beide Ganzzahlen, und wenn für eines von beiden dieses Bit nicht gesetzt ist, ist die Addition sicher.

Dies wäre sogar noch schneller, wenn Sie die Maske in einem Konstruktor vorinitialisieren, da sie sich nie ändert.

Steztric
quelle
5
Das ist nicht richtig. Das Tragen kann Bits aus niedrigeren Positionen bringen, die einen Überlauf verursachen. Erwägen Sie das Hinzufügen UINT_MAX + 1. Nach dem Maskieren awird das High-Bit gesetzt, aber es 1wird Null und daher kehrt die Funktion zurück true. Die Addition ist sicher - dennoch werden Sie direkt zum Überlauf geleitet.
das Schwein
0

mozilla::CheckedInt<T>Bietet eine überlaufgeprüfte Ganzzahlmathematik für den Ganzzahltyp T(unter Verwendung der Compiler-Intrinsics für clang und gcc, sofern verfügbar). Der Code ist unter der MPL 2.0 und hängt von drei ( IntegerTypeTraits.h, Attributes.hund Compiler.h) andere Kopf nur Nicht-Standard - Bibliothek - Header sowie Mozilla-spezifische Behauptung Maschinen . Sie möchten wahrscheinlich die Assertion-Maschinerie ersetzen, wenn Sie den Code importieren.

hsivonen
quelle
-1

MSalters Antwort ist eine gute Idee.

Wenn die Ganzzahlberechnung erforderlich ist (aus Genauigkeitsgründen), aber Gleitkomma verfügbar ist, können Sie Folgendes tun:

uint64_t foo(uint64_t a, uint64_t b) {
    double dc;

    dc = pow(a, b);

    if (dc < UINT_MAX) {
       return (powu64(a, b));
    }
    else {
      // Overflow
    }
}
Frank Szczerba
quelle
Normalerweise würde ich sagen, dass das Wiederholen der Berechnung im Gleitkomma eine schlechte Idee ist, aber für diesen speziellen Fall der Potenzierung a ^ c kann es durchaus effizienter sein. Aber der Test sollte sein (c * log(a) < max_log), woconst double max_log = log(UINT_MAX)
Toby Speight
-1

Der x86-Befehlssatz enthält einen vorzeichenlosen Multiplikationsbefehl, der das Ergebnis in zwei Registern speichert. Um diesen Befehl von C zu verwenden, kann man den folgenden Code in ein 64-Bit-Programm (GCC) schreiben:

unsigned long checked_imul(unsigned long a, unsigned long b) {
  unsigned __int128 res = (unsigned __int128)a * b;
  if ((unsigned long)(res >> 64))
    printf("overflow in integer multiply");
  return (unsigned long)res;
}

Für ein 32-Bit-Programm muss das Ergebnis 64-Bit und die Parameter 32-Bit sein.

Eine Alternative besteht darin, das Compiler-abhängige Intrinsic zu verwenden, um das Flag-Register zu überprüfen. Die GCC-Dokumentation für den intrinsischen Überlauf finden Sie in 6.56 Integrierte Funktionen zum Durchführen von Arithmetik mit Überlaufprüfung .

Pauli Nieminen
quelle
1
Sie sollten den vorzeichenlosen 128-Bit-Typ verwenden __uint128, um einen vorzeichenbehafteten Überlauf und eine Verschiebung eines negativen Werts nach rechts zu vermeiden.
Chqrlie
Was sind "compilerabhängige Instinkte" und "Überlaufinstinkte" ? Meinen Sie " intrinsische Funktionen " ? Haben Sie eine Referenz? (Bitte antworten Sie, indem Sie Ihre Antwort bearbeiten , nicht hier in den Kommentaren (falls zutreffend).)
Peter Mortensen
-3
#include <stdio.h>
#include <stdlib.h>

#define MAX 100 

int mltovf(int a, int b)
{
    if (a && b) return abs(a) > MAX/abs(b);
    else return 0;
}

main()
{
    int a, b;

    for (a = 0; a <= MAX; a++)
        for (b = 0; b < MAX; b++) {

        if (mltovf(a, b) != (a*b > MAX)) 
            printf("Bad calculation: a: %d b: %d\n", a, b);

    }
}
Scott Franco
quelle
-3

Eine saubere Möglichkeit wäre, alle Operatoren (insbesondere + und *) zu überschreiben und vor dem Ausführen der Vorgänge auf einen Überlauf zu prüfen.

Brian R. Bondy
quelle
6
Außer dass Sie Operatoren für integrierte Typen nicht überschreiben können. Sie müssten dafür eine Klasse schreiben und den Client-Code neu schreiben, um ihn zu verwenden.
Blaisorblade
-3

Es hängt davon ab, wofür Sie es verwenden. Wenn Sie eine vorzeichenlose lange Addition (DWORD) oder Multiplikation durchführen, ist die beste Lösung die Verwendung von ULARGE_INTEGER.

ULARGE_INTEGER ist eine Struktur aus zwei DWORDs. Auf den vollen Wert kann als "QuadPart" zugegriffen werden, während auf das hohe DWORD als "HighPart" und auf das niedrige DWORD als "LowPart" zugegriffen wird.

Zum Beispiel:

DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
    ULARGE_INTEGER a, b;

    b.LowPart = Value_A;  // A 32 bit value(up to 32 bit)
    b.HighPart = 0;
    a.LowPart = Value_B;  // A 32 bit value(up to 32 bit)
    a.HighPart = 0;

    a.QuadPart += b.QuadPart;

    // If  a.HighPart
    // Then a.HighPart contains the overflow (carry)

    return (a.LowPart + a.HighPart)

    // Any overflow is stored in a.HighPart (up to 32 bits)
Spyros Panaoussis
quelle
6
Leider ist dies eine reine Windows-Lösung. Andere Plattformen haben nicht ULARGE_INTEGER.
Mysticial
-3

Um eine vorzeichenlose Multiplikation durchzuführen, ohne auf tragbare Weise überzulaufen, kann Folgendes verwendet werden:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
   product += multiplicand;
   if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
   int ctZeroes;
   if( value == 0 ) return 32;
   ctZeroes = 1;
   if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
   if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
   if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
   if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
   ctZeroes -= x >> 31;
   return ctZeroes;
}
Tyler Durden
quelle
-4

Der einfache Weg, um auf Überlauf zu testen, besteht darin, eine Validierung durchzuführen, indem überprüft wird, ob der aktuelle Wert kleiner als der vorherige Wert ist. Angenommen, Sie hatten eine Schleife, um die Potenzen von 2 zu drucken:

long lng;
int n;
for (n = 0; n < 34; ++n)
{
   lng = pow (2, n);
   printf ("%li\n", lng);
}

Das Hinzufügen einer Überlaufprüfung, wie ich sie beschrieben habe, führt zu folgenden Ergebnissen:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
    lng = pow (2, n);
    if (lng <= lng_prev)
    {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
    }
    printf ("%li\n", lng);
    lng_prev = lng;
}

Es funktioniert sowohl für vorzeichenlose Werte als auch für positive und negative vorzeichenbehaftete Werte.

Wenn Sie etwas Ähnliches tun möchten <=, um Werte zu verringern, anstatt Werte zu erhöhen, würden Sie das Vorzeichen umdrehen , um dies zu erreichen >=, vorausgesetzt, das Verhalten des Unterlaufs ist das gleiche wie das Verhalten des Überlaufs. Um ehrlich zu sein, ist dies ungefähr so ​​portabel, wie Sie es ohne Zugriff auf das Überlauf-Flag einer CPU erhalten (und dies würde Inline-Assembly-Code erfordern, sodass Ihr Code ohnehin nicht für alle Implementierungen portierbar ist).

Dustin
quelle
9
Wenn ein vorzeichenbehafteter Wert überläuft, ist das Verhalten Ihres Programms undefiniert. Es ist nicht garantiert, um zu wickeln.
David Stone