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 ++ .
quelle
-ftrapv
bewirkt, dass bei einem (vorzeichenbehafteten) Ganzzahlüberlauf ein SIGABRT generiert wird. Siehe hier .clz
Anweisung 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 Falllog(sizeof(int)*8)
Anweisungen erfordert.Antworten:
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).
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:
Bei der Division ( mit Ausnahme der
INT_MIN
und-1
Sonderfall), gibt es keine Möglichkeit , gehen überINT_MIN
oderINT_MAX
.quelle
x >= 0
-x > 0
wird ausreichen (wennx == 0
, dannx + a
kann er aus offensichtlichen Gründen nicht überlaufen).if ((a < INT_MIN / x))
Test ist zu spät.if (x == -1)
Zuerst wird ein Test benötigt.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:
Bei der Multiplikation ergeben zwei beliebige Operanden (höchstens) die Summe der Bits der Operanden. Zum Beispiel:
In ähnlicher Weise können Sie die maximale Größe des Ergebnisses
a
auf folgende Potenz schätzenb
:(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:
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
highestOneBitPosition
Funktion 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).quelle
log2
, aber das wäre für jemanden ohne mathematischen Hintergrund nicht unbedingt so offensichtlich.multiplication_is_safe
0x8000 * 0x10000
würde Überlauf (Bitpositionen sind 16 + 17 = 33, was > 32 ist ), obwohl dies nicht0x8000 * 0x10000 = 0x80000000
der 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
, ...0x8000 * 0x10000
ist nach dieser Definition nicht "sicher", obwohl es sich als in Ordnung herausstellt.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:
In der Clang-Dokumentation wird nicht angegeben, ob
c_test
das übergelaufene Ergebnis enthalten ist, wenn ein Überlauf aufgetreten ist. In der GCC-Dokumentation wird dies jedoch angegeben. Angesichts der Tatsache, dass diese beiden gerne__builtin
kompatibel sind, kann man davon ausgehen, dass Clang auch so funktioniert.Es gibt einen
__builtin
fü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
:u
für nicht signiert oders
für signiert ;add
,sub
odermul
;l
Suffix bedeutet, dass die Operandenint
s sind; manl
meintlong
; zweil
s bedeutenlong 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_overflow
und__builtin_mul_overflow
. Diese funktionieren auch bei Typen, die kleiner als sindint
.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 Sieaddcarry_uNN
und verwendensubborrow_uNN
(wobei NN die Anzahl der Bits ist, wieaddcarry_u8
odersubborrow_u64
). Ihre Unterschrift ist etwas stumpf:c_in
/b_in
ist 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.
quelle
__builtin_sub_overflow
ist definitiv nicht in Clang 3.4.__builtin_add_overflow
und Freunde bereits auf Clang 3.8 verfügbar sein.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:
quelle
b == ULONG_MAX / a
? Dann kann es noch passen, vorausgesetzt, esa
teilt sichULONG_MAX
ohne Rest.Warnung: GCC kann eine Überlaufprüfung beim Kompilieren mit optimieren
-O2
. Die Option-Wall
gibt Ihnen in einigen Fällen eine Warnung wieaber nicht in diesem Beispiel:
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
-fwrapv
lö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.
quelle
for(int k = 0; k < 5; k++) {...}
sollte also eine Warnung ausgelöst werden?k
können zur Kompilierungszeit leicht bestimmt werden. Der Compiler muss keine Annahmen treffen.n
kleiner als 32 ist, bevor ein Verschiebungsbefehl ausgegeben wird, der nur die unteren 5 Bits vonn
? Verwendet .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.
quelle
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:
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:
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:
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).
quelle
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.
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.quelle
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.
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
0xFF
wird0xFFFFFFFF
und0x80
wird0x80000000
und wird schließlichuint16_t
einuint64_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
calloc
Implementierungen normalerweise sicher, dass die Parameter nicht überlaufen, wenn sie multipliziert werden, um die endgültige Größe zu erhalten.quelle
Am einfachsten ist es, Ihr
unsigned long
s inunsigned long long
s 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ähntSIGFPE
. Das wäre ideal, abgesehen von den fiesen Stellen im Handbuch:Ein bisschen schade wirklich.
quelle
ULONG_MAX
was einfacher zu tippen und portabler ist als Hardcodierung0x100000000
.long
undlong long
haben dieselbe Größe (z. B. bei vielen 64-Bit-Compilern).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:
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:
Eine effizientere und kostengünstigere Methode zum Erkennen eines Multiplikationsüberlaufs ist:
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.
quelle
x+y>=256
undvalue=x+y-256
. Weily<256
immer wahr gilt, ist (y-256) negativ und sovalue < x
ist es immer wahr. Der Beweis für den nicht überfüllten Fall ist ziemlich ähnlich.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 Sieor
die Werte nicht eingeben, können Sie nicht zwischen einem Operanden und dem Übertragsbit Null und einem Operanden0xffffffff
und dem Übertragsbit Eins unterscheiden.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
-ftrapv
scheint 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.quelle
Überprüfen Sie bei vorzeichenlosen Ganzzahlen einfach, ob das Ergebnis kleiner als eines der Argumente ist:
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:
quelle
char result = (char)127 + (char)3;
wäre -126; kleiner als beide Operanden.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:
Erhalten Sie die Konstanten, die die größtmöglichen und kleinstmöglichen Werte für den Typ MAXVALUE und MINVALUE darstellen.
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.
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.
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.
Ansonsten kein Überlauf.
Signierter Überlauftest, Multiplikation und Division:
Erhalten Sie die Konstanten, die die größtmöglichen und kleinstmöglichen Werte für den Typ MAXVALUE und MINVALUE darstellen.
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.
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.
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).
quelle
1.0e-200 / 1.0e200
wäre ein Beispiel für einen tatsächlichen Unterlauf, vorausgesetzt, IEEE verdoppelt sich. Der korrekte Begriff hier ist stattdessen negativer Überlauf. </ Pedantic>1/INT_MAX
könnte dies als Unterlauf angesehen werden, aber die Sprache schreibt einfach eine Kürzung auf Null vor.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.
quelle
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:
quelle
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 ).
(edi und esi registrieren sich in meinem Code)) und gibt das Ergebnis oder 0 zurück, wenn ein Überlauf aufgetreten ist.
Prüfung:
Verknüpfen Sie das Programm mit der asm-Objektdatei. In meinem Fall fügen Sie es in Qt Creator
LIBS
einer .pro-Datei hinzu.quelle
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.
quelle
Probieren Sie dieses Makro aus, um das Überlaufbit von 32-Bit-Maschinen zu testen (angepasst an die Lösung von Angel Sinigersky).
Ich habe es als Makro definiert, weil sonst das Überlaufbit überschrieben worden wäre.
Nachfolgend finden Sie eine kleine Anwendung mit dem obigen Codesegment:
quelle
_MSC_VER
obwohl MS-Kompilierungen den Code alle ablehnen).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).
quelle
Dem stimme ich nicht zu. Sie können eine Inline-Assemblersprache schreiben und eine
jo
Anweisung (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 as
undinfo gcc
.quelle
Um die Antwort von Head Geek zu erweitern, gibt es einen schnelleren Weg, dies zu tun
addition_is_safe
.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.
quelle
UINT_MAX + 1
. Nach dem Maskierena
wird das High-Bit gesetzt, aber es1
wird Null und daher kehrt die Funktion zurücktrue
. Die Addition ist sicher - dennoch werden Sie direkt zum Überlauf geleitet.mozilla::CheckedInt<T>
Bietet eine überlaufgeprüfte Ganzzahlmathematik für den GanzzahltypT
(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.h
undCompiler.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.quelle
MSalters Antwort ist eine gute Idee.
Wenn die Ganzzahlberechnung erforderlich ist (aus Genauigkeitsgründen), aber Gleitkomma verfügbar ist, können Sie Folgendes tun:
quelle
(c * log(a) < max_log)
, woconst double max_log = log(UINT_MAX)
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:
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 .
quelle
__uint128
, um einen vorzeichenbehafteten Überlauf und eine Verschiebung eines negativen Werts nach rechts zu vermeiden.quelle
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.
quelle
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:
quelle
ULARGE_INTEGER
.Um eine vorzeichenlose Multiplikation durchzuführen, ohne auf tragbare Weise überzulaufen, kann Folgendes verwendet werden:
quelle
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:
Das Hinzufügen einer Überlaufprüfung, wie ich sie beschrieben habe, führt zu folgenden Ergebnissen:
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).quelle