Jak wykryć przepełnienie wielokrotności liczby całkowitej bez znaku?

Pisałem program w C ++, aby znaleźć wszystkie rozwiązania z ^b = c , gdzie , b i c razem wykorzystać wszystkie cyfry 0-9 dokładnie raz. Program zwracane nad wartości i B , i pobiegł rutynowej cyfra liczenia za każdym razem na o , b i a ^{, b} , aby sprawdzić, czy warunek ten został spełniony, cyfry.

Jednakże, uboczne rozwiązania mogą być generowane podczas ^b przelewa limit całkowitej. Skończyło się na sprawdzeniu tego za pomocą kodu, takiego jak:

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

Czy istnieje lepszy sposób testowania przepełnienia? Wiem, że niektóre układy mają wewnętrzną flagę, która jest ustawiana, gdy nastąpi przepełnienie, ale nigdy nie widziałem, aby można było uzyskać do niej dostęp za pośrednictwem C lub C ++.

Uważaj, że podpisane int przepełnienie jest niezdefiniowanym zachowaniem w C i C ++ , a zatem musisz je wykryć bez powodowania go. Aby zapoznać się z przepełnieniem podpisu int przed dodaniem, zobacz Wykrywanie przepełnienia podpisu w C / C ++ .

Widzę, że używasz liczb całkowitych bez znaku. Z definicji w C (nie wiem o C ++) arytmetyka bez znaku nie przepełnia się ... więc, przynajmniej w przypadku C, masz rację:

W przypadku liczb całkowitych ze znakiem, gdy wystąpi przepełnienie, wystąpiło niezdefiniowane zachowanie (UB), a program może zrobić wszystko (na przykład: renderować testy niejednoznaczne). 

#include <limits.h>

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

Aby utworzyć zgodny program, musisz przetestować przepełnienie przed wygenerowaniem wspomnianego przepełnienia. Metodę można również stosować z liczbami całkowitymi bez znaku:

// 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 */;

Do podziału (z wyjątkiem INT_MINi -1szczególny przypadek), nie ma żadnej możliwości podchodząc INT_MINlub INT_MAX.

Nie jest to sposób, aby określić, czy operacja jest zlecenie przelewu, wykorzystując pozycje najbardziej znaczących bitów w jednym z argumentów i trochę podstawowej wiedzy binarnie matematyki.

Dodatkowo dwa dowolne operandy spowodują (najwyżej) jeden bit więcej niż najwyższy jeden największy argument. Na przykład:

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

W przypadku mnożenia dowolne dwa operandy będą skutkowały (co najwyżej) sumą bitów operandów. Na przykład:

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

Podobnie możesz oszacować maksymalny rozmiar wyniku ado potęgi bpodobnej:

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

(Oczywiście zamień liczbę bitów na docelową liczbę całkowitą).

Nie jestem pewien najszybszego sposobu określenia pozycji najwyższego bitu w liczbie, oto metoda brute-force:

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

To nie jest idealne, ale da ci to dobry pomysł, czy jakieś dwie liczby mogą się przepełnić przed wykonaniem operacji. Nie wiem, czy byłoby to szybsze niż zwykłe sprawdzenie wyniku w sposób sugerowany przez ciebie z powodu pętli w highestOneBitPositionfunkcji, ale może (zwłaszcza jeśli wcześniej wiedziałeś, ile bitów było w operandach).

Clang 3.4+ i GCC 5+ oferują sprawdzone wbudowane arytmetyki. Oferują one bardzo szybkie rozwiązanie tego problemu, szczególnie w porównaniu z testami bezpieczeństwa do testów bitowych.

Na przykład w pytaniu OP działałoby to tak:

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
}

Dokumentacja Clanga nie określa, czy c_testzawiera przepełniony wynik w przypadku przepełnienia, ale dokumentacja GCC mówi, że tak. Biorąc pod uwagę, że ci dwaj lubią być __builtinkompatybilni, prawdopodobnie bezpiecznie jest założyć, że tak właśnie działa Clang.

__builtinDla każdej operacji arytmetycznej istnieje przepełnienie (dodawanie, odejmowanie, mnożenie) z podpisanymi i niepodpisanymi wariantami dla liczb całkowitych, długich i długich. Składnia nazwy to __builtin_[us](operation)(l?l?)_overflow:

• udla niepodpisane lub sza podpisane ;
• Działanie to jeden add, sublub mul;
• brak lprzyrostka oznacza, że ​​operandy są ints; jeden loznacza long; dwa ls oznaczają long long.

Tak byłoby w przypadku sprawdzonego dodawania długiej liczby całkowitej __builtin_saddl_overflow. Pełna lista znajduje się na stronie dokumentacji Clanga .

GCC 5+ i Clang 3.8+ dodatkowo oferują rodzajowe pomocy poleceń wbudowanych, że praca bez określania typu wartości: __builtin_add_overflow, __builtin_sub_overflowi __builtin_mul_overflow. Działają również na typach mniejszych niż int.

Wbudowane są niższe niż najlepsze dla platformy. Na x86 sprawdzają flagi przenoszenia, przepełnienia i podpisują flagi.

Plik cl.exe programu Visual Studio nie ma bezpośrednich odpowiedników. W przypadku niepodpisanych dodatków i odejmowań, w tym <intrin.h>pozwoli ci użyć addcarry_uNNi subborrow_uNN(gdzie NN jest liczbą bitów, jak addcarry_u8lub subborrow_u64). Ich podpis jest nieco tępy:

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_inoznacza flagę carry / borrow na wejściu, a wartością zwracaną jest carry / borrow na wyjściu. Wygląda na to, że nie ma odpowiedników dla podpisanych operacji lub mnożenia.

W przeciwnym razie Clang dla Windows jest teraz gotowy do produkcji (wystarczająco dobry dla Chrome), więc może to być również opcja.

Niektóre kompilatory zapewniają dostęp do flagi przepełnienia liczb całkowitych w CPU, którą można następnie przetestować, ale nie jest to standard.

Możesz także przetestować możliwość przepełnienia przed wykonaniem mnożenia:

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

Ostrzeżenie: GCC może zoptymalizować kontrolę przepełnienia podczas kompilacji -O2. Ta opcja -Wallwyświetli ostrzeżenie w niektórych przypadkach, takich jak

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

ale nie w tym przykładzie:

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

Jedynym bezpiecznym sposobem jest sprawdzenie przepełnienia przed jego wystąpieniem, jak opisano w dokumencie CERT , a jego systematyczne stosowanie byłoby niezwykle uciążliwe.

Kompilacja z -fwrapvrozwiązuje problem, ale wyłącza niektóre optymalizacje.

Desperacko potrzebujemy lepszego rozwiązania. Myślę, że kompilator powinien domyślnie wyświetlać ostrzeżenie podczas przeprowadzania optymalizacji, która opiera się na braku przepełnienia. Obecna sytuacja pozwala kompilatorowi zoptymalizować kontrolę przepełnienia, co moim zdaniem jest niedopuszczalne.

Clang obsługuje teraz dynamiczne kontrole przepełnienia zarówno dla liczb całkowitych ze znakiem, jak i bez znaku. Zobacz przełącznik -fsanitize = liczba całkowita . Na razie jest to jedyny kompilator C ++ z całkowicie obsługiwanym dynamicznym sprawdzaniem przepełnienia do celów debugowania.

Widzę, że wiele osób odpowiedziało na pytanie o przepełnienie, ale chciałem rozwiązać jego pierwotny problem. Powiedział, że problemem jest znalezienie ^b = c, tak aby wszystkie cyfry były używane bez powtarzania. Ok, nie o to pytał w tym poście, ale nadal uważam, że konieczne było przestudiowanie górnej granicy problemu i wyciągnięcie wniosku, że nigdy nie będzie musiał obliczać ani wykrywać przepełnienia (uwaga: nie jestem biegły z matematyki, więc zrobiłem to krok po kroku, ale wynik końcowy był tak prosty, że może mieć prostą formułę).

Głównym punktem jest to, że górna granica, której wymaga problem dla a, b lub c, wynosi 98.765.432. W każdym razie, zaczynając od podzielenia problemu na trywialne i nietrywialne części:

• x ⁰ == 1 (wszystkie permutacje 9, 8, 7, 6, 5, 4, 3, 2 są rozwiązaniami)
• x ¹ == x (niemożliwe rozwiązanie)
• 0 ^b == 0 (niemożliwe rozwiązanie)
• 1 ^b == 1 (niemożliwe rozwiązanie)
• a ^b , a> 1, b> 1 (nietrywialne)

Teraz musimy tylko pokazać, że żadne inne rozwiązanie nie jest możliwe, a poprawne są tylko permutacje (a następnie kod do ich wydrukowania jest trywialny). Wracamy do górnej granicy. W rzeczywistości górna granica wynosi c ≤ 98,765,432. Jest to górna granica, ponieważ jest to największa liczba z 8 cyframi (łącznie 10 cyfr minus 1 dla każdego a i b). Ta górna granica jest tylko dla c, ponieważ granice aib muszą być znacznie niższe z powodu wykładniczego wzrostu, jak możemy obliczyć, zmieniając b od 2 do górnej granicy:

    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

Zauważ, na przykład ostatnia linia: mówi, że 1,97 ^ 27 ~ 98M. Na przykład 1 ^ 27 == 1 i 2 ^ 27 == 134.217.728 i to nie jest rozwiązanie, ponieważ ma 9 cyfr (2> 1,97, więc jest faktycznie większe niż to, co powinno być przetestowane). Jak widać, kombinacje dostępne do testowania aib są naprawdę małe. Dla b == 14 musimy spróbować 2 i 3. Dla b == 3 zaczynamy od 2 i zatrzymujemy się na 462. Wszystkie wyniki są mniejsze niż ~ 98 mln.

Teraz wystarczy przetestować wszystkie powyższe kombinacje i poszukać tych, które nie powtarzają żadnych cyfr:

    ['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)

Żadne z nich nie pasuje do problemu (co można również zobaczyć przez brak „0”, „1”, ..., „9”).

Przykładowy kod, który go rozwiązuje, jest następujący. Zauważ też, że jest napisane w Pythonie, nie dlatego, że wymaga liczb całkowitych o dowolnej precyzji (kod nie oblicza niczego większego niż 98 milionów), ale ponieważ odkryliśmy, że liczba testów jest tak mała, że ​​powinniśmy używać języka wysokiego poziomu, aby korzystaj z wbudowanych kontenerów i bibliotek (uwaga: kod ma 28 wierszy).

    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)

Oto „nieprzenośne” rozwiązanie tego pytania. Procesory Intel x86 i x64 mają tak zwany rejestr EFLAGS , który jest wypełniany przez procesor po każdej operacji arytmetycznej na liczbach całkowitych. Pomiń tutaj szczegółowy opis. Odpowiednimi flagami są flaga „Przepełnienie” (maska ​​0x800) i flaga „Przenoszenie” (maska ​​0x1). Aby interpretować je poprawnie, należy rozważyć, czy operandy są typu podpisanego czy niepodpisanego.

Oto praktyczny sposób sprawdzenia flag z C / C ++. Poniższy kod będzie działał na Visual Studio 2005 lub nowszym (zarówno 32-bitowym, jak i 64-bitowym), a także na GNU C / C ++ 64-bitowym.

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

Gdyby argumenty zostały zwielokrotnione bez przepełnienia, otrzymalibyśmy wartość 0 od query_intel_eflags(0x801), tzn. Nie ustawiono flag przenoszenia ani przepełnienia. W podanym przykładowym kodzie main () występuje przepełnienie, a obie flagi są ustawione na 1. To sprawdzenie nie oznacza żadnych dalszych obliczeń, więc powinno być dość szybkie.

Jeśli masz typ danych większy niż ten, który chcesz przetestować (powiedzmy, że dodajesz 32-bit i masz typ 64-bitowy), to wykryje, czy nastąpiło przepełnienie. Mój przykład dotyczy dodawania 8-bitowego. Ale można go zwiększyć.

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

Opiera się na pojęciach wyjaśnionych na tej stronie: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

Dla przykładu 32-bitowego 0xFFstaje się 0xFFFFFFFFi 0x80staje się, 0x80000000a w końcu uint16_tstaje się uint64_t.

UWAGA : wychwytuje to przepełnienie dodawania / odejmowania liczb całkowitych i zdałem sobie sprawę, że twoje pytanie obejmuje mnożenie. W takim przypadku podział jest prawdopodobnie najlepszym podejściem. Jest to zwykle sposób, w jaki callocimplementacje upewniają się, że parametry nie przepełniają się, ponieważ są mnożone w celu uzyskania ostatecznego rozmiaru.

Najprostszym sposobem jest konwersja unsigned longs na unsigned long longs, pomnożenie i porównanie wyniku do 0x100000000LL.

Prawdopodobnie przekonasz się, że jest to bardziej wydajne niż dzielenie, jak w przykładzie.

Aha, i będzie działać zarówno w C, jak i C ++ (jak oznaczyłeś pytanie w obu).

Właśnie oglądałem instrukcję glibc . Jest tam wzmianka o pułapce przepełnienia liczb całkowitych ( FPE_INTOVF_TRAP) jako części SIGFPE. Byłoby idealnie, oprócz nieprzyjemnych fragmentów instrukcji:

FPE_INTOVF_TRAP Przepełnienie liczb całkowitych (niemożliwe w programie C, chyba że włączysz pułapkę przepełnienia w sposób specyficzny dla sprzętu).

Trochę wstydu.

Oto naprawdę szybki sposób na wykrycie przepełnienia przynajmniej dla dodatków, co może dać przewagę w mnożeniu, dzieleniu i sile.

Chodzi o to, że właśnie dlatego, że procesor po prostu pozwoli wartości zawinąć się do zera, a C / C ++ jest wyodrębniany z dowolnego konkretnego procesora, możesz:

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

To zapewnia, że ​​jeśli jeden argument jest równy zero, a drugi nie, to przepełnienie nie zostanie fałszywie wykryte i jest znacznie szybsze niż wiele operacji NOT / XOR / AND / testowych, jak wcześniej sugerowano.

Jak wskazano, takie podejście, choć lepsze niż inne bardziej skomplikowane sposoby, jest nadal możliwe do zoptymalizowania. Poniżej znajduje się wersja oryginalnego kodu zawierającego optymalizację:

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

Bardziej wydajnym i tanim sposobem na wykrycie przepełnienia jest:

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

Powoduje to albo UINT32_MAX przy przepełnieniu, albo wynik mnożenia. W tym przypadku jest to ściśle niezdefiniowane zachowanie, aby umożliwić kontynuowanie mnożenia dla podpisanych liczb całkowitych.

Nie możesz uzyskać dostępu do flagi przepełnienia z C / C ++.

Niektóre kompilatory pozwalają wstawiać instrukcje pułapek do kodu. Na GCC jest to opcja -ftrapv.

Jedyną przenośną i niezależną od kompilatora rzeczą, którą możesz zrobić, jest samodzielne sprawdzenie przepełnienia. Tak jak w twoim przykładzie.

-ftrapvWydaje się jednak, że nic nie robi na x86 przy użyciu najnowszego GCC. Sądzę, że jest to pozostałość po starej wersji lub specyficzna dla innej architektury. Spodziewałem się, że kompilator wstawi kod operacji INTO po każdym dodaniu. Niestety tego nie robi.

W przypadku liczb całkowitych bez znaku sprawdź, czy wynik jest mniejszy niż jeden z argumentów:

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

W przypadku liczb całkowitych ze znakiem można sprawdzić znaki argumentów i wyniku.

Liczby całkowite różnych znaków nie mogą się przepełnić, a liczby całkowite tego samego znaku są przepełnione tylko wtedy, gdy wynik jest innego znaku:

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

Musiałem odpowiedzieć na to samo pytanie dla liczb zmiennoprzecinkowych, w których maskowanie i przesuwanie bitów nie wygląda obiecująco. Podejście, na którym się zdecydowałem, dotyczy prac dla liczb podpisanych i niepodpisanych, liczb całkowitych i zmiennoprzecinkowych. Działa nawet wtedy, gdy nie ma większego typu danych do promowania w obliczeniach pośrednich. Nie jest najbardziej wydajny dla wszystkich tych typów, ale ponieważ działa na wszystkie, warto go użyć.

Podpisany test przepełnienia, dodawanie i odejmowanie:

1. Uzyskaj stałe reprezentujące największe i najmniejsze możliwe wartości dla typu, MAXVALUE i MINVALUE.

2. Oblicz i porównaj znaki operandów.

   za. Jeśli którakolwiek wartość jest równa zero, to ani dodawanie, ani odejmowanie nie może się przelać. Pomiń pozostałe testy.

   b. Jeśli znaki są przeciwne, dodanie nie może się przelać. Pomiń pozostałe testy.

   do. Jeśli znaki są takie same, odejmowanie nie może się przelać. Pomiń pozostałe testy.

3. Test na dodatnie przepełnienie wartości MAXVALUE.

   za. Jeśli oba znaki są dodatnie i MAKSYMALNA - A <B, wówczas dodawanie przepełni się.

   b. Jeśli znak B jest ujemny, a MAXVALUE - A <-B, wówczas odejdzie przepełnienie.

4. Test pod kątem ujemnego przepełnienia MINVALUE.

   za. Jeśli oba znaki są ujemne, a WARTOŚĆ MINIMALNA - A> B, wówczas dodawanie przepełni się.

   b. Jeśli znak A jest ujemny, a WARTOŚĆ MINOWA - A> B, wówczas odejdzie przepełnienie.

5. W przeciwnym razie nie ma przelewu.

Podpisany test przepełnienia, mnożenie i dzielenie:

1. Uzyskaj stałe reprezentujące największe i najmniejsze możliwe wartości dla typu, MAXVALUE i MINVALUE.

2. Oblicz i porównaj wielkości (wartości bezwzględne) operandów z jednym. (Poniżej załóżmy, że A i B to te wielkości, a nie podpisane oryginały).

   za. Jeśli jedna z wartości wynosi zero, mnożenie nie może się przepełnić, a dzielenie da zero lub nieskończoność.

   b. Jeśli jedna z wartości jest równa jeden, mnożenie i dzielenie nie mogą się przepełnić.

   do. Jeśli wielkość jednego operandu jest mniejsza niż jeden, a drugiego jest większa niż jeden, mnożenie nie może się przepełnić.

   re. Jeśli zarówno wielkości są mniejsze niż jeden, podział nie może się przepełnić.

3. Test na dodatnie przepełnienie wartości MAXVALUE.

   za. Jeśli oba argumenty są większe niż jeden i MAXVALUE / A <B, mnożenie się przepełni.

   b. Jeśli B jest mniejsze niż jeden, a MAXVALUE * B <A, podział zostanie przepełniony.

4. W przeciwnym razie nie ma przelewu.

Uwaga: Minimalne przepełnienie MINVALUE jest obsługiwane przez 3, ponieważ przyjęliśmy wartości bezwzględne. Jeśli jednak ABS (MINWARTOŚĆ)> MAXWARTOŚĆ, będziemy mieli rzadkie fałszywe wyniki dodatnie.

Testy niedomiaru są podobne, ale obejmują EPSILON (najmniejsza liczba dodatnia większa od zera).

Firma CERT opracowała nowe podejście do wykrywania i zgłaszania przekroczenia liczby podpisanych liczb całkowitych, owijania liczb całkowitych bez znaku i obcinania liczb całkowitych, wykorzystując model liczb całkowitych „jak gdyby” z nieograniczonym zasięgiem (AIR). CERT opublikował raport techniczny opisujący model i opracował działający prototyp oparty na GCC 4.4.0 i GCC 4.5.0.

Model liczb całkowitych AIR generuje wartość równoważną wartości, która zostałaby uzyskana przy użyciu liczb całkowitych o nieograniczonym zakresie, lub powoduje naruszenie ograniczenia środowiska wykonawczego. W przeciwieństwie do poprzednich modeli liczb całkowitych, liczby całkowite AIR nie wymagają precyzyjnych pułapek, w związku z czym nie psują ani nie hamują większości istniejących optymalizacji.

Innym interesującym narzędziem jest IOC: Integer Overflow Checker for C / C ++ .

Jest to poprawiony kompilator Clanga , który dodaje kontrole do kodu w czasie kompilacji.

Otrzymasz wynik wyglądający tak:

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

Innym wariantem rozwiązania wykorzystującego język asemblera jest procedura zewnętrzna. Ten przykład mnożenia liczb całkowitych bez znaku za pomocą g ++ i fasm pod Linux x64.

Ta procedura zwielokrotnia dwa argumenty liczb całkowitych bez znaku (32 bity) (zgodnie ze specyfikacją dla amd64 (sekcja 3.2.3 Przekazywanie parametrów ).

Jeśli klasa jest INTEGER, używany jest następny dostępny rejestr sekwencji% rdi,% rsi,% rdx,% rcx,% r8 i% r9

(edi i esi rejestrują się w moim kodzie)) i zwraca wynik lub 0, jeśli wystąpiło przepełnienie.

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

Test:

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

Połącz program z plikiem obiektu asm. W moim przypadku w Qt Creator dodaj go do LIBSpliku .pro.

Oblicz wyniki z podwójnymi. Mają 15 cyfr znaczących. Twoje wymaganie ma twardą górną granicę c na 10 ⁸  - może mieć maksymalnie 8 cyfr. W związku z tym wynik będzie dokładny, jeśli znajdzie się w zakresie, i w przeciwnym razie nie przepełni się.

Wypróbuj to makro, aby przetestować bit przepełnienia 32-bitowych maszyn (dostosował rozwiązanie Angel Sinigersky)

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

Zdefiniowałem go jako makro, ponieważ w przeciwnym razie bit przepełnienia zostałby nadpisany.

Kolejna jest mała aplikacja z powyższym segmentem kodu:

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

Przechwytywanie przepełnień liczb całkowitych w C wskazuje na rozwiązanie bardziej ogólne niż to omówione przez CERT (jest bardziej ogólne pod względem obsługiwanych typów), nawet jeśli wymaga pewnych rozszerzeń GCC (nie wiem, jak szeroko są obsługiwane).

Nie możesz uzyskać dostępu do flagi przepełnienia z C / C ++.

Nie zgadzam się z tym. Możesz napisać wbudowany język asemblera i użyćjo instrukcji (przepełnienie skoku), zakładając, że jesteś na x86, aby przechwycić przepełnienie. Oczywiście twój kod nie byłby już przenośny dla innych architektur.

Spójrz na info asiinfo gcc .

Aby rozwinąć odpowiedź Head Geek, istnieje szybszy sposób na zrobienie tego 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 );
}

Korzysta z bezpiecznej architektury maszyn, ponieważ 64-bitowe i 32-bitowe liczby całkowite bez znaku będą nadal działać poprawnie. Zasadniczo tworzę maskę, która zamaskuje wszystko oprócz najbardziej znaczącego fragmentu. Następnie maskuję obie liczby całkowite, a jeśli któryś z nich nie ma ustawionego tego bitu, dodawanie jest bezpieczne.

Byłoby to jeszcze szybsze, jeśli wstępnie zainicjujesz maskę w jakimś konstruktorze, ponieważ nigdy się nie zmienia.

mozilla::CheckedInt<T>zapewnia sprawdzanie przepełnienia matematyki liczb całkowitych dla typu liczb całkowitych T(przy użyciu wbudowanych kompilatorów w clang i gcc, jeśli są dostępne). Kod jest pod MPL 2.0 i zależy od trzech ( IntegerTypeTraits.h, Attributes.hi Compiler.h) inne tylko nagłówek niestandardowe nagłówki biblioteki plus Mozilla specyficzne maszyny twierdzenie . Prawdopodobnie chcesz wymienić maszynę do potwierdzania, jeśli zaimportujesz kod.

Odpowiedź MSaltera to dobry pomysł.

Jeśli wymagane jest obliczanie liczb całkowitych (dla precyzji), ale dostępny jest zmiennoprzecinkowy, możesz zrobić coś takiego:

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
    }
}

Zestaw instrukcji x86 zawiera niepodpisaną instrukcję mnożenia, która przechowuje wynik w dwóch rejestrach. Aby skorzystać z tej instrukcji z C, można napisać następujący kod w 64-bitowym programie (GCC):

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

W przypadku programu 32-bitowego wynik musi być 64-bitowy, a parametry 32-bitowe.

Alternatywą jest użycie funkcji wewnętrznej zależnej od kompilatora do sprawdzenia rejestru flag. Dokumentację GCC wewnętrzną przepełnienia można znaleźć w 6.56 Wbudowanych funkcji do wykonywania arytmetyki z kontrolą przepełnienia .

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

    }
}

Czystym sposobem na to byłoby zastąpienie wszystkich operatorów (w szczególności + i *) i sprawdzenie, czy nie występuje przepełnienie przed wykonaniem operacji.

To zależy do czego go używasz. Dokonując dodawania lub mnożenia bez znaku długiego (DWORD), najlepszym rozwiązaniem jest użycie ULARGE_INTEGER.

ULARGE_INTEGER jest strukturą dwóch DWORD. Dostęp do pełnej wartości można uzyskać jako „QuadPart”, podczas gdy wysoki DWORD jest dostępny jako „HighPart”, a niski DWORD jest dostępny jako „LowPart”.

Na przykład:

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)

Aby wykonać mnożenie bez znaku bez przepełnienia w przenośny sposób, można użyć:

... /* 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;
}

Prostym sposobem na sprawdzenie przepełnienia jest sprawdzenie poprawności poprzez sprawdzenie, czy bieżąca wartość jest mniejsza niż poprzednia. Załóżmy na przykład, że masz pętlę do wydrukowania potęg 2:

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

Dodanie przelewu sprawdzającego sposób, w jaki opisałem, powoduje:

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

Działa z wartościami bez znaku, a także z wartościami dodatnimi i ujemnymi.

Oczywiście, jeśli chciałbyś zrobić coś podobnego dla zmniejszania wartości zamiast zwiększania wartości, odwróciłbyś <=znak, aby to zrobić >=, zakładając, że zachowanie niedomiaru jest takie samo, jak zachowanie przelania. Szczerze mówiąc, jest to tak przenośne, jak to możliwe, bez dostępu do flagi przepełnienia procesora (i to wymagałoby wbudowanego kodu asemblowania, co sprawiłoby, że kod nie byłby przenośny między implementacjami).