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

Clang unterstützt nun dynamische Überlaufprüfungen sowohl für vorzeichenbehaftete als auch für vorzeichenlose Ganzzahlen. Siehe die -fsanitize=ganzzahlig Schalter. Im Moment ist er der einzige C++-Compiler mit vollständig unterstützter dynamischer Überlaufprüfung für Debug-Zwecke.

Answer 2

Hier ist ein wirklich schneller Weg, um einen Überlauf zumindest bei Additionen zu erkennen, was einen Hinweis auf Multiplikation, Division und Potenzierung geben könnte.

Die Idee dahinter ist, dass man genau deshalb, weil der Prozessor den Wert einfach auf Null zurücklaufen lässt und C/C++ von jedem spezifischen Prozessor abstrahiert, dies tun kann:

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

Dadurch wird sichergestellt, dass ein Überlauf nicht fälschlicherweise erkannt wird, wenn ein Operand Null ist und der andere nicht, und es ist wesentlich schneller als eine Reihe von NOT/XOR/AND/Test-Operationen, wie zuvor vorgeschlagen.

Wie bereits erwähnt, ist dieser Ansatz zwar besser als andere, aufwändigere Methoden, aber immer noch optimierbar. Der folgende Text 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 billigere Methode zur Erkennung eines Multiplikationsüberlaufs ist:

uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
    (a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

Das Ergebnis ist entweder UINT32_MAX bei Überlauf oder das Ergebnis der Multiplikation. Es ist ein absolut undefiniertes Verhalten, die Multiplikation von ganzen Zahlen mit Vorzeichen in diesem Fall zuzulassen.

Dabei wird die partielle multiplikative Zerlegung nach der Karatsuba-Methode verwendet, um die hohen 32 Bits der 64-Bit-Multiplikation zu berechnen und zu prüfen, ob eines von ihnen gesetzt werden sollte, um zu wissen, ob die 32-Bit-Multiplikation überläuft.

Wenn Sie C++ verwenden, können Sie dies in ein nettes kleines Lambda verwandeln, um den Überlauf zu berechnen, so dass das Innenleben des Detektors verborgen wird:

uint32_t x, y;
const bool overflow
{
    [](const uint32_t x, const uint32_t y) noexcept -> bool
    {
        const uint32_t a{(x >> 16U) * uint16_t(y)};
        const uint32_t b{uint16_t(x) * (y >> 16U)};
        return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
    }(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};

Answer 3

Ich sehe, dass viele Leute die Frage nach dem Überlauf beantwortet haben, aber ich wollte auf sein ursprüngliches Problem eingehen. Er sagte, das Problem sei, eine b \=c so, dass alle Ziffern ohne Wiederholung verwendet werden. Ok, das ist nicht das, was er in diesem Beitrag gefragt hat, aber ich denke immer noch, dass es notwendig war, die obere Schranke des Problems zu studieren und zu dem Schluss zu kommen, dass er niemals einen Überlauf berechnen oder erkennen muss (Anmerkung: Ich bin nicht gut in Mathe, also habe ich das Schritt für Schritt gemacht, aber das Endergebnis war so einfach, dass es eine einfache Formel haben könnte).

Der wichtigste Punkt ist, dass die Obergrenze, die das Problem für a, b oder c erfordert, 98.765.432 beträgt. Wie auch immer, wir beginnen damit, das Problem in einen trivialen und einen nicht-trivialen Teil aufzuteilen:

• 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, um sie zu drucken, trivial). Wir gehen zurück zur oberen Schranke. Eigentlich ist die Obergrenze c 98.765.432. Es ist die obere Schranke, weil es die größte Zahl mit 8 Ziffern ist (10 Ziffern insgesamt minus 1 für jedes a und b). Diese obere Schranke gilt nur für c, weil die Schranken für a und b wegen des exponentiellen Wachstums viel niedriger sein müssen, wie wir berechnen können, wenn wir b von 2 bis zur oberen Schranke 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: Dort steht, dass 1,97^27 ~98M. Also, zum Beispiel, 1^27 == 1 und 2^27 == 134.217.728 und das ist keine Lösung, weil es 9 Ziffern hat (2 > 1.97, also ist es eigentlich größer als das, was getestet werden sollte). Wie man sieht, sind die verfügbaren Kombinationen zum Testen von a und b wirklich klein. Für b == 14 müssen wir 2 und 3 ausprobieren. Für b == 3 fangen wir bei 2 an und hören bei 462 auf. Alle Ergebnisse sind garantiert kleiner als ~98M.

Testen Sie nun alle obigen Kombinationen und suchen Sie nach denjenigen, bei denen sich 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).

Es folgt ein Beispielcode, der diese Aufgabe löst. Beachten Sie auch, dass er in Python geschrieben ist, nicht weil er beliebig genaue Zahlen benötigt (der Code berechnet nichts, was größer als 98 Millionen ist), sondern weil wir herausgefunden haben, dass die Anzahl der Tests so klein ist, dass wir eine Hochsprache verwenden sollten, um ihre eingebauten Container und Bibliotheken zu nutzen (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)

Answer 4

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

Hier ist ein praktischer Weg, um die Flags von C/C++ zu überprüfen. Der folgende Code funktioniert mit Visual Studio 2005 oder neuer (sowohl 32 als auch 64 Bit), sowie 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ürde man den Rückgabewert 0 von query_intel_eflags(0x801) d.h. weder der Übertrags- noch der Überlaufmerker sind gesetzt. Im mitgelieferten Beispielcode von main() kommt es zu einem Überlauf und beide Flags werden auf 1 gesetzt. Diese Prüfung erfordert keine weiteren Berechnungen und sollte daher recht schnell sein.

Answer 5

Wenn Sie einen Datentyp haben, der größer ist als der zu prüfende (z. B. wenn Sie eine 32-Bit-Addition durchführen und einen 64-Bit-Typ haben), dann wird dies erkennen, ob ein Überlauf aufgetreten ist. Mein Beispiel bezieht sich auf eine 8-Bit-Addition. Es lässt sich aber hochskalieren.

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

Sie 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 wird 0xFFFFFFFF y 0x80 wird 0x80000000 und schließlich uint16_t wird ein uint64_t .

ANMERKUNG : Dies fängt ganzzahlige Additions-/Subtraktionsüberläufe ab, und ich habe erkannt, dass Ihre Frage die Multiplikation betrifft. In diesem Fall ist die Division wahrscheinlich der beste Ansatz. Dies ist in der Regel ein Weg, der calloc Implementierungen stellen sicher, dass die Parameter nicht überlaufen, wenn sie multipliziert werden, um die endgültige Größe zu erhalten.