Bagaimana cara saya mendeteksi kelebihan integer bilangan bulat yang tidak ditandatangani?

Saya sedang menulis sebuah program dalam C ++ untuk menemukan semua solusi dari a ^b = c , di mana sebuah , b dan c bersama-sama menggunakan semua angka 0-9 tepat sekali. Program dilingkarkan di atas nilai-nilai yang dan b , dan berlari digit penghitungan rutin setiap kali di sebuah , b dan a ^b untuk memeriksa apakah kondisi digit puas.

Namun, solusi palsu dapat dihasilkan ketika sebuah ^b meluap batas integer. Saya akhirnya memeriksa ini menggunakan kode seperti:

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

Apakah ada cara yang lebih baik untuk menguji luapan? Saya tahu bahwa beberapa chip memiliki flag internal yang diatur ketika terjadi overflow, tetapi saya belum pernah melihatnya diakses melalui C atau C ++.

Waspadalah bahwa overflow yang ditandatangani int adalah perilaku tidak terdefinisi dalam C dan C ++ , dan karenanya Anda harus mendeteksinya tanpa benar-benar menyebabkannya. Untuk limpahan int yang ditandatangani sebelum penambahan, lihat Mendeteksi limpahan yang ditandatangani di C / C ++ .

Saya melihat Anda menggunakan bilangan bulat yang tidak ditandatangani. Menurut definisi, di C (saya tidak tahu tentang C ++), aritmatika yang tidak ditandatangani tidak melimpah ... jadi, setidaknya untuk C, poin Anda bisa diperdebatkan :)

Dengan bilangan bulat yang ditandatangani, setelah terjadi overflow, perilaku tidak terdefinisi (UB) telah terjadi dan program Anda dapat melakukan apa saja (misalnya: render tes tidak meyakinkan). 

#include <limits.h>

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

Untuk membuat program yang sesuai, Anda perlu menguji untuk overflow sebelum membuat kata overflow. Metode ini dapat digunakan dengan bilangan bulat tidak bertanda juga:

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

Untuk pembagian (kecuali untuk INT_MINdan -1kasus khusus), tidak ada kemungkinan untuk beralih INT_MINatau INT_MAX.

Ada adalah cara untuk menentukan apakah operasi cenderung meluap, menggunakan posisi yang paling signifikan satu-bit dalam operan dan pengetahuan biner-matematika dasar sedikit.

Sebagai tambahan, setiap dua operan akan menghasilkan (paling banyak) satu bit lebih banyak dari operand tertinggi satu bit terbesar. Sebagai contoh:

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

Untuk penggandaan, setiap dua operan akan menghasilkan (paling banyak) jumlah bit dari operan. Sebagai contoh:

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

Demikian pula, Anda dapat memperkirakan ukuran maksimum hasil ahingga kekuatan bseperti ini:

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

(Pengganti jumlah bit untuk target integer Anda, tentu saja.)

Saya tidak yakin dengan cara tercepat untuk menentukan posisi bit tertinggi dalam sebuah angka, berikut ini adalah metode brute-force:

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

Itu tidak sempurna, tetapi itu akan memberi Anda ide yang baik apakah ada dua angka yang bisa meluap sebelum Anda melakukan operasi. Saya tidak tahu apakah itu akan lebih cepat daripada hanya memeriksa hasilnya seperti yang Anda sarankan, karena loop dalam highestOneBitPositionfungsi, tetapi mungkin (terutama jika Anda tahu berapa banyak bit di operan sebelumnya).

Dentang 3.4+ dan GCC 5+ menawarkan builtin aritmatika yang diperiksa. Mereka menawarkan solusi yang sangat cepat untuk masalah ini, terutama jika dibandingkan dengan pemeriksaan keamanan pengujian bit.

Sebagai contoh dalam pertanyaan OP, itu akan berfungsi seperti ini:

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
}

Dokumentasi Dentang tidak menentukan apakah c_testberisi hasil meluap jika terjadi overflow, tetapi dokumentasi GCC mengatakan itu. Mengingat bahwa keduanya suka __builtin-compatible, mungkin aman untuk berasumsi bahwa ini adalah cara kerja dentang juga.

Ada __builtinuntuk setiap operasi aritmatika yang dapat meluap (penjumlahan, pengurangan, penggandaan), dengan varian yang ditandatangani dan tidak ditandatangani, untuk ukuran int, ukuran panjang, dan ukuran panjang yang panjang. Sintaks untuk namanya adalah __builtin_[us](operation)(l?l?)_overflow:

• uuntuk tidak ditandatangani atau suntuk ditandatangani ;
• operasi adalah salah satu add, subatau mul;
• no lsuffix berarti operan adalah ints; satu lberarti long; dua ls berarti long long.

Jadi untuk penambahan bilangan bulat panjang bertanda tangan yang dicentang, itu akan menjadi __builtin_saddl_overflow. Daftar lengkap dapat ditemukan di halaman dokumentasi Dentang .

GCC 5 + dan dentang 3.8+ juga menawarkan builtin generik yang bekerja tanpa menentukan jenis nilai-nilai: __builtin_add_overflow, __builtin_sub_overflowdan __builtin_mul_overflow. Ini juga bekerja pada jenis yang lebih kecil dari int.

Builtin lebih rendah ke apa yang terbaik untuk platform. Pada x86, mereka memeriksa carry, overflow, dan tanda bendera.

Cl.exe Visual Studio tidak memiliki padanan langsung. Untuk penambahan dan pengurangan yang tidak ditandatangani, termasuk <intrin.h>akan memungkinkan Anda untuk menggunakan addcarry_uNNdan subborrow_uNN(di mana NN adalah jumlah bit, suka addcarry_u8atau subborrow_u64). Tanda tangan mereka agak tumpul:

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_inadalah flag carry / meminjam pada input, dan nilai kembali adalah carry / pinjam pada output. Tampaknya tidak memiliki padanan untuk operasi atau multiplikasi yang ditandatangani.

Kalau tidak, Dentang untuk Windows sekarang sudah siap produksi (cukup baik untuk Chrome), sehingga bisa menjadi pilihan juga.

Beberapa kompiler menyediakan akses ke flag integer overflow di CPU yang dapat Anda uji tetapi ini bukan standar.

Anda juga bisa menguji kemungkinan overflow sebelum Anda melakukan perkalian:

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

Peringatan: GCC dapat mengoptimalkan jauh pemeriksaan luapan saat dikompilasi -O2. Opsi -Wallakan memberi Anda peringatan dalam beberapa kasus seperti

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

tetapi tidak dalam contoh ini:

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

Satu-satunya cara yang aman adalah memeriksa luapan sebelum terjadi, seperti yang dijelaskan dalam makalah CERT , dan ini akan sangat membosankan untuk digunakan secara sistematis.

Kompilasi dengan -fwrapvmemecahkan masalah, tetapi menonaktifkan beberapa optimasi.

Kami sangat membutuhkan solusi yang lebih baik. Saya pikir kompiler harus mengeluarkan peringatan secara default ketika membuat optimasi yang mengandalkan overflow tidak terjadi. Situasi saat ini memungkinkan kompiler untuk mengoptimalkan cek overflow, yang menurut saya tidak dapat diterima.

Dentang sekarang mendukung pemeriksaan overflow dinamis untuk bilangan bulat yang ditandatangani dan tidak ditandatangani. Lihat sakelar -fsanitize = integer . Untuk saat ini, ini adalah satu-satunya kompiler C ++ dengan dynamic overflow yang didukung sepenuhnya untuk keperluan debug.

Saya melihat bahwa banyak orang menjawab pertanyaan tentang meluap, tetapi saya ingin mengatasi masalah aslinya. Dia mengatakan masalahnya adalah menemukan ^b = c sehingga semua digit digunakan tanpa mengulangi. Oke, bukan itu yang dia tanyakan dalam posting ini, tapi saya masih berpikir bahwa itu perlu untuk mempelajari batas atas masalah dan menyimpulkan bahwa dia tidak perlu menghitung atau mendeteksi luapan (catatan: Saya tidak cakap dalam matematika jadi saya melakukan langkah demi langkah ini, tetapi hasil akhirnya sangat sederhana sehingga ini mungkin memiliki rumus sederhana).

Poin utama adalah bahwa batas atas yang dibutuhkan oleh masalah untuk a, b atau c adalah 98.765.432. Pokoknya, mulailah dengan memecah masalah di bagian sepele dan non sepele:

• x ⁰ == 1 (semua permutasi 9, 8, 7, 6, 5, 4, 3, 2 adalah solusi)
• x ¹ == x (tidak ada solusi yang mungkin)
• 0 ^b == 0 (tidak ada solusi yang mungkin)
• 1 ^b == 1 (tidak ada solusi yang mungkin)
• a ^b , a> 1, b> 1 (tidak sepele)

Sekarang kita hanya perlu menunjukkan bahwa tidak ada solusi lain yang mungkin dan hanya permutasi yang valid (dan kemudian kode untuk mencetaknya adalah sepele). Kami kembali ke batas atas. Sebenarnya batas atas adalah c ≤ 98.765.432. Ini adalah batas atas karena ini adalah angka terbesar dengan 8 digit (total 10 digit minus 1 untuk masing-masing a dan b). Batas atas ini hanya untuk c karena batas untuk a dan b harus jauh lebih rendah karena pertumbuhan eksponensial, seperti yang dapat kita hitung, bervariasi b dari 2 hingga batas atas:

    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

Perhatikan, misalnya baris terakhir: dikatakan bahwa 1,97 ^ 27 ~ 98M. Jadi, misalnya, 1 ^ 27 == 1 dan 2 ^ 27 == 134.217.728 dan itu bukan solusi karena memiliki 9 digit (2> 1,97 sehingga sebenarnya lebih besar dari apa yang harus diuji). Seperti dapat dilihat, kombinasi yang tersedia untuk pengujian a dan b sangat kecil. Untuk b == 14, kita perlu mencoba 2 dan 3. Untuk b == 3, kita mulai dari 2 dan berhenti di 462. Semua hasil yang diberikan kurang dari ~ 98M.

Sekarang coba saja semua kombinasi di atas dan cari yang tidak mengulangi angka apa pun:

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

Tak satu pun dari mereka cocok dengan masalah (yang juga bisa dilihat dengan tidak adanya '0', '1', ..., '9').

Contoh kode yang menyelesaikannya mengikuti. Perhatikan juga bahwa ini ditulis dengan Python, bukan karena membutuhkan bilangan bulat presisi yang sewenang-wenang (kode tidak menghitung apa pun yang lebih besar dari 98 juta), tetapi karena kami menemukan bahwa jumlah tes sangat kecil sehingga kami harus menggunakan bahasa tingkat tinggi untuk memanfaatkan wadah dan pustaka bawaannya (juga perhatikan: kode memiliki 28 baris).

    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)

Berikut adalah solusi "non-portabel" untuk pertanyaan tersebut. Intel x86 dan x64 CPU memiliki apa yang disebut EFLAGS-register , yang diisi oleh prosesor setelah setiap operasi aritmatika integer. Saya akan melewatkan deskripsi terperinci di sini. Bendera yang relevan adalah Bendera "Overflow" (mask 0x800) dan "Carry" Flag (mask 0x1). Untuk menafsirkannya dengan benar, orang harus mempertimbangkan apakah operan bertipe ditandatangani atau tidak.

Berikut ini adalah cara praktis untuk memeriksa flag dari C / C ++. Kode berikut akan bekerja pada Visual Studio 2005 atau lebih baru (baik 32 dan 64 bit), serta pada 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);
}

Jika operan dikalikan tanpa overflow, Anda akan mendapatkan nilai balik 0 dari query_intel_eflags(0x801), yaitu, carry atau flag overflow tidak diatur. Dalam kode contoh utama yang disediakan (), terjadi overflow dan kedua flag diset ke 1. Pemeriksaan ini tidak menyiratkan perhitungan lebih lanjut, jadi harus cukup cepat.

Jika Anda memiliki tipe data yang lebih besar daripada yang ingin Anda uji (mis. Anda menambahkan 32-bit dan Anda memiliki tipe 64-bit), maka ini akan mendeteksi jika terjadi overflow. Contoh saya adalah untuk menambahkan 8-bit. Tapi itu bisa ditingkatkan.

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

Ini didasarkan pada konsep-konsep yang dijelaskan pada halaman ini: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

Sebagai contoh 32-bit, 0xFFmenjadi 0xFFFFFFFFdan 0x80menjadi 0x80000000dan akhirnya uint16_tmenjadi uint64_t.

CATATAN : ini menangkap penambahan / pengurangan bilangan bulat bilangan bulat, dan saya menyadari bahwa pertanyaan Anda melibatkan multiplikasi. Dalam hal ini, pembagian kemungkinan merupakan pendekatan terbaik. Ini biasanya merupakan cara callocimplementasi memastikan bahwa parameter tidak meluap ketika mereka dikalikan untuk mendapatkan ukuran akhir.

Cara paling sederhana adalah mengubah unsigned longs Anda menjadi unsigned long longs, lakukan penggandaan Anda, dan bandingkan hasilnya dengan 0x100000000LL.

Anda mungkin akan menemukan bahwa ini lebih efisien daripada melakukan pembagian seperti yang telah Anda lakukan dalam contoh Anda.

Oh, dan itu akan bekerja di C dan C ++ (karena Anda telah menandai pertanyaan dengan keduanya).

Baru saja melihat manual glibc . Ada yang menyebutkan jebakan integer overflow ( FPE_INTOVF_TRAP) sebagai bagian dari SIGFPE. Itu akan ideal, terlepas dari bagian-bagian buruk dalam manual:

FPE_INTOVF_TRAP Integer overflow (tidak mungkin dalam program C kecuali Anda mengaktifkan trapping overflow dengan cara yang spesifik perangkat keras).

Sedikit memalukan kok.

Berikut adalah cara yang sangat cepat untuk mendeteksi overflow untuk setidaknya penambahan, yang mungkin memberikan petunjuk untuk multiplikasi, pembagian, dan kekuatan.

Idenya adalah persis karena prosesor hanya akan membiarkan nilai membungkus kembali ke nol dan bahwa C / C ++ akan diabstraksi dari prosesor tertentu, Anda dapat:

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

Ini keduanya memastikan bahwa jika satu operan nol dan satu tidak, maka overflow tidak akan terdeteksi secara salah dan secara signifikan lebih cepat daripada banyak operasi BUKAN / XOR / DAN / seperti yang disarankan sebelumnya.

Seperti yang ditunjukkan, pendekatan ini, meskipun lebih baik daripada cara lain yang lebih rumit, masih dapat dioptimalkan. Berikut ini adalah revisi dari kode asli yang berisi optimisasi:

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

Cara yang lebih efisien dan murah untuk mendeteksi multiplication overflow adalah:

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

Ini menghasilkan UINT32_MAX saat overflow, atau hasil perkalian. Ini adalah perilaku yang tidak ditentukan untuk memungkinkan perkalian untuk melanjutkan untuk bilangan bulat yang ditandatangani dalam kasus ini.

Anda tidak dapat mengakses flag overflow dari C / C ++.

Beberapa kompiler memungkinkan Anda untuk memasukkan instruksi trap ke dalam kode. Pada GCC opsinya adalah -ftrapv.

Satu-satunya hal yang portabel dan kompiler yang dapat Anda lakukan adalah memeriksa sendiri kelebihannya. Sama seperti yang Anda lakukan dalam contoh Anda.

Namun, -ftrapvtampaknya tidak melakukan apa pun pada x86 menggunakan GCC terbaru. Saya kira itu adalah sisa dari versi lama atau khusus untuk beberapa arsitektur lain. Saya mengharapkan kompiler untuk memasukkan INTO opcode setelah setiap penambahan. Sayangnya tidak melakukan ini.

Untuk bilangan bulat yang tidak ditandatangani, cukup periksa bahwa hasilnya lebih kecil dari salah satu argumen:

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

Untuk bilangan bulat yang ditandatangani, Anda dapat memeriksa tanda-tanda argumen dan hasilnya.

Bilangan bulat dari tanda yang berbeda tidak dapat melimpah, dan bilangan bulat dari tanda yang sama hanya jika hasilnya berupa tanda yang berbeda:

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

Saya perlu menjawab pertanyaan yang sama untuk angka floating point, di mana bit masking dan shifting tidak terlihat menjanjikan. Pendekatan yang saya tetapkan pada karya untuk angka-angka titik yang ditandatangani dan tidak ditandatangani, bilangan bulat dan mengambang. Ini berfungsi bahkan jika tidak ada tipe data yang lebih besar untuk dipromosikan ke untuk perhitungan menengah. Ini bukan yang paling efisien untuk semua jenis ini, tetapi karena itu bekerja untuk mereka semua, itu layak digunakan.

Tes Overflow, Penambahan, dan Pengurangan yang ditandatangani:

1. Dapatkan konstanta yang mewakili nilai terbesar dan terkecil yang mungkin untuk tipe, MAXVALUE dan MINVALUE.

2. Hitung dan bandingkan tanda-tanda operan.

   Sebuah. Jika salah satu nilai nol, maka penambahan atau pengurangan tidak bisa meluap. Lewati tes yang tersisa.

   b. Jika tanda-tandanya berlawanan, maka penambahan tidak bisa meluap. Lewati tes yang tersisa.

   c. Jika tanda-tandanya sama, maka pengurangan tidak bisa meluap. Lewati tes yang tersisa.

3. Tes untuk aliran MAXVALUE positif.

   Sebuah. Jika kedua tanda positif dan MAXVALUE - A <B, maka penambahan akan melimpah.

   b. Jika tanda B negatif dan MAXVALUE - A <-B, maka pengurangan akan melimpah.

4. Tes untuk luapan negatif MINVALUE.

   Sebuah. Jika kedua tanda negatif dan MINVALUE - A> B, maka penambahan akan melimpah.

   b. Jika tanda A negatif dan MINVALUE - A> B, maka pengurangan akan melimpah.

5. Kalau tidak, tidak ada luapan.

Tes Overflow, Multiplikasi dan Divisi yang ditandatangani:

1. Dapatkan konstanta yang mewakili nilai terbesar dan terkecil yang mungkin untuk tipe, MAXVALUE dan MINVALUE.

2. Hitung dan bandingkan besaran (nilai absolut) dari operan dengan satu. (Di bawah ini, anggap A dan B adalah magnitudo ini, bukan yang asli yang ditandatangani.)

   Sebuah. Jika salah satu nilai adalah nol, perkalian tidak dapat meluap, dan pembagian akan menghasilkan nol atau tak terhingga.

   b. Jika salah satu nilai adalah satu, multiplikasi dan pembagian tidak dapat meluap.

   c. Jika besarnya satu operan di bawah satu dan yang lainnya lebih besar dari satu, multiplikasi tidak dapat meluap.

   d. Jika besarnya keduanya kurang dari satu, pembagian tidak dapat meluap.

3. Tes untuk aliran MAXVALUE positif.

   Sebuah. Jika kedua operan lebih besar dari satu dan MAXVALUE / A <B, maka multiplikasi akan melimpah.

   b. Jika B kurang dari satu dan MAXVALUE * B <A, maka pembagian akan melimpah.

4. Kalau tidak, tidak ada luapan.

Catatan: Overflow minimum MINVALUE ditangani oleh 3, karena kami mengambil nilai absolut. Namun, jika ABS (MINVALUE)> MAXVALUE, maka kami akan memiliki beberapa false positive yang langka.

Tes untuk aliran bawah serupa, tetapi melibatkan EPSILON (angka positif terkecil yang lebih besar dari nol).

CERT telah mengembangkan pendekatan baru untuk mendeteksi dan melaporkan limpasan bilangan bulat bertanda tangan, pembungkus bilangan bulat tak bertanda, dan pemotongan bilangan bulat menggunakan model bilangan bulat "seolah-olah" tak berhingga (AIR). CERT telah menerbitkan laporan teknis yang menggambarkan model dan menghasilkan prototipe kerja berdasarkan GCC 4.4.0 dan GCC 4.5.0.

Model integer AIR baik menghasilkan nilai yang setara dengan yang akan diperoleh dengan menggunakan bilangan bulat tak terhingga atau hasil dalam pelanggaran kendala runtime. Tidak seperti model integer sebelumnya, integer AIR tidak memerlukan jebakan yang tepat, dan akibatnya tidak merusak atau menghambat sebagian besar optimasi yang ada.

Alat lain yang menarik adalah IOC: An Integer Overflow Checker untuk C / C ++ .

Ini adalah kompilasi Dentang tambalan , yang menambahkan pemeriksaan ke kode pada waktu kompilasi.

Anda mendapatkan hasil seperti ini:

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

Varian lain dari solusi, menggunakan bahasa assembly, adalah prosedur eksternal. Contoh ini untuk perkalian integer tak bertanda menggunakan g ++ dan fasm di Linux x64.

Prosedur ini mengalikan dua argumen integer yang tidak ditandatangani (32 bit) (sesuai dengan spesifikasi untuk amd64 (bagian 3.2.3 Parameter Passing ).

Jika kelas adalah INTEGER, register yang tersedia berikutnya dari urutan% rdi,% rsi,% rdx,% rcx,% r8, dan% r9 digunakan

(edi dan esi mendaftar dalam kode saya)) dan mengembalikan hasilnya atau 0 jika terjadi overflow.

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

Uji:

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

Tautkan program dengan file objek asm. Dalam kasus saya, di Qt Creator , tambahkan ke LIBSdalam file .pro.

Hitung hasilnya dengan ganda. Mereka memiliki 15 digit signifikan. Persyaratan Anda memiliki batas atas yang keras pada c dari 10 ⁸  - ia dapat memiliki paling banyak 8 digit. Oleh karena itu, hasilnya akan tepat jika berada dalam jangkauan, dan tidak akan meluap sebaliknya.

Coba makro ini untuk menguji bit overflow dari mesin 32-bit (mengadaptasi solusi Angel Sinigersky)

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

Saya mendefinisikannya sebagai makro karena kalau tidak bit overflow akan ditimpa.

Berikutnya adalah aplikasi kecil dengan kode segmen di atas:

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

Menangkap Integer Overflows di C menunjukkan solusi yang lebih umum daripada yang dibahas oleh CERT (ini lebih umum dalam hal jenis yang ditangani), bahkan jika itu memerlukan beberapa ekstensi GCC (saya tidak tahu seberapa luas mereka didukung).

Anda tidak dapat mengakses flag overflow dari C / C ++.

Saya tidak setuju dengan ini. Anda bisa menulis beberapa bahasa rakitan inline dan menggunakan joinstruksi (lompatan lompatan) dengan asumsi Anda berada di x86 untuk menjebak overflow. Tentu saja, kode Anda tidak lagi portabel untuk arsitektur lain.

Lihatlah info asdan info gcc.

Untuk memperluas jawaban Kepala Geek, ada cara yang lebih cepat untuk melakukan 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 );
}

Ini menggunakan arsitektur mesin aman, dalam bahwa integer 64-bit dan 32-bit masih akan bekerja dengan baik. Pada dasarnya, saya membuat topeng yang akan menutupi semua kecuali bagian yang paling signifikan. Kemudian, saya menutupi kedua bilangan bulat, dan jika salah satu dari mereka tidak memiliki set bit, maka penambahan aman.

Ini akan lebih cepat jika Anda melakukan inisialisasi topeng di beberapa konstruktor, karena itu tidak pernah berubah.

mozilla::CheckedInt<T>menyediakan matematika integer berlebih yang diperiksa untuk tipe integer T(menggunakan intrinsik kompiler pada dentang dan gcc jika tersedia). Kode ini berada di bawah MPL 2.0 dan tergantung pada tiga ( IntegerTypeTraits.h, Attributes.hdan Compiler.h) header perpustakaan non-standar hanya header lainnya ditambah mesin pernyataan spesifik Mozilla . Anda mungkin ingin mengganti mesin asersi jika Anda mengimpor kode.

Jawaban MSalter adalah ide yang bagus.

Jika perhitungan integer diperlukan (untuk presisi), tetapi floating point tersedia, Anda bisa melakukan sesuatu seperti:

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

Set instruksi x86 termasuk instruksi multiplikasi yang tidak ditandatangani yang menyimpan hasilnya ke dua register. Untuk menggunakan instruksi dari C, seseorang dapat menulis kode berikut dalam program 64-bit (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;
}

Untuk program 32-bit, kita perlu membuat hasilnya 64 bit dan parameter 32 bit.

Alternatifnya adalah menggunakan intrinsik yang bergantung pada kompiler untuk memeriksa register flag. Dokumentasi GCC untuk intrinsik overflow dapat ditemukan dari 6.56 Fungsi Bawaan untuk Melakukan Aritmatika dengan Memeriksa Overflow .

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

    }
}

Cara yang bersih untuk melakukannya adalah dengan menimpa semua operator (+ dan * khususnya) dan memeriksa overflow sebelum melakukan operasi.

Tergantung untuk apa Anda menggunakannya. Melakukan penambahan atau perkalian unsigned long (DWORD), solusi terbaik adalah dengan menggunakan ULARGE_INTEGER.

ULARGE_INTEGER adalah struktur dua DWORD. Nilai penuh dapat diakses sebagai "QuadPart" sementara DWORD tinggi diakses sebagai "HighPart" dan DWORD rendah diakses sebagai "LowPart".

Sebagai contoh:

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)

Untuk melakukan perkalian tanpa tanda tangan tanpa meluap dengan cara portabel berikut ini dapat digunakan:

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

Cara sederhana untuk menguji overflow adalah dengan melakukan validasi dengan memeriksa apakah nilai saat ini kurang dari nilai sebelumnya. Misalnya, misalkan Anda memiliki loop untuk mencetak kekuatan 2:

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

Menambahkan limpahan memeriksa cara saya menggambarkan hasil dalam ini:

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

Ini berfungsi untuk nilai yang tidak ditandatangani serta nilai yang ditandatangani positif dan negatif.

Tentu saja, jika Anda ingin melakukan sesuatu yang serupa untuk menurunkan nilai alih-alih meningkatkan nilai, Anda akan membalik <=tanda untuk membuatnya >=, dengan asumsi perilaku underflow sama dengan perilaku overflow. Dalam semua kejujuran, itu tentang portabel karena Anda akan mendapatkan tanpa akses ke flag melimpah CPU (dan itu akan membutuhkan kode perakitan inline, tetap membuat kode Anda non-portabel di seluruh implementasi).