Integer Overflow

#include <iostream>
#include <climits>
#include <cstdint>
#include <string>
#include <algorithm>

// 1) Signed overflow adalah UB — compiler bisa asumsikan tidak terjadi
int naive_mul(int a, int b) {
    return a * b;   // bila a*b > INT_MAX → UB
}

// 2) Pengecekan sebelum operasi — aman
bool safe_mul(int a, int b, int& out) {
    if (a > 0 && b > 0 && a > INT_MAX / b) return false;
    if (a > 0 && b < 0 && b < INT_MIN / a) return false;
    if (a < 0 && b > 0 && a < INT_MIN / b) return false;
    if (a < 0 && b < 0 && a < INT_MAX / b) return false;  // neg * neg
    // a == 0 atau b == 0 → hasil 0, aman
    out = a * b;
    return true;
}

// 3) Unsigned overflow — well-defined (wrap modulo 2^N)
void demo_unsigned_wrap() {
    unsigned int u = 0;
    std::cout << "u = " << u << ", u - 1 = " << (u - 1) << " (wrap to UINT_MAX)\n";

    unsigned char c = 255;
    c = c + 1;   // assignment kembali ke unsigned char — wrap to 0
    std::cout << "255 + 1 (unsigned char) = " << (int)c << " (wrap to 0)\n";
}

// 4) Cast ke wider type untuk cek
bool safe_add_ll(long long a, long long b, long long& out) {
    if (b > 0 && a > LLONG_MAX - b) return false;
    if (b < 0 && a < LLONG_MIN - b) return false;
    out = a + b;
    return true;
}

// 5) __int128 untuk big number (GCC extension)
void demo_int128() {
    __int128 big = (__int128)1 << 100;   // 2^100
    __int128 two_60 = (__int128)1 << 60;
    __int128 prod = big * 1;             // tetap aman

    // Cetak __int128 manual (tidak ada iostream support)
    auto print128 = [](__int128 v) {
        if (v == 0) { std::cout << '0'; return; }
        bool neg = v < 0;
        if (neg) v = -v;
        std::string s;
        while (v > 0) { s += char('0' + (int)(v % 10)); v /= 10; }
        if (neg) s += '-';
        std::reverse(s.begin(), s.end());
        std::cout << s;
    };
    std::cout << "2^100 = ";
    print128(big);
    std::cout << "\n2^60  = ";
    print128(two_60);
    std::cout << "\nprod  = ";
    print128(prod);
    std::cout << '\n';
}

// 6) Modular arithmetic — pencegahan overflow dengan mod
const long long MOD = 1'000'000'007LL;

long long mulmod(long long a, long long b, long long m) {
    // a, b < m < 2^63 → a*b bisa overflow long long
    // Solusi 1: __int128
    return (long long)((__int128)a * b % m);
}

long long mulmod_safe(long long a, long long b, long long m) {
    // Solusi 2: russian peasant — tanpa __int128
    a %= m; b %= m;
    long long res = 0;
    while (b > 0) {
        if (b & 1) {
            res += a;
            if (res >= m) res -= m;
        }
        a <<= 1;
        if (a >= m) a -= m;
        b >>= 1;
    }
    return res;
}

int main() {
    // Naive (UB bila overflow)
    int x = INT_MAX;
    std::cout << "INT_MAX = " << x << '\n';
    std::cout << "naive_mul(INT_MAX, 2) = " << naive_mul(x, 2) << " (UB!)\n";

    // Safe check
    int out;
    if (safe_mul(x, 2, out)) {
        std::cout << "safe_mul ok: " << out << '\n';
    } else {
        std::cout << "safe_mul: overflow detected\n";
    }
    if (safe_mul(3, 4, out)) {
        std::cout << "safe_mul(3,4) = " << out << '\n';
    }

    // Unsigned wrap
    demo_unsigned_wrap();

    // 64-bit add
    long long lo;
    if (safe_add_ll(LLONG_MAX, 1, lo)) std::cout << "add ok: " << lo << '\n';
    else                                std::cout << "LLONG_MAX + 1 overflow\n";

    // __int128
    demo_int128();

    // Modular arithmetic
    long long a = 1'000'000'000LL, b = 1'000'000'000LL;
    std::cout << "mulmod(" << a << ", " << b << ", " << MOD << ") = "
              << mulmod(a, b, MOD) << '\n';
    std::cout << "mulmod_safe = " << mulmod_safe(a, b, MOD) << '\n';

    // Demo: signed overflow UB (sengaja — pragma untuk sembunyikan warning demo)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Woverflow"
    int big_mul = 100000 * 100000;   // 10^10 — overflow int!
#pragma GCC diagnostic pop
    std::cout << "100000 * 100000 (int)   = " << big_mul << " (WRONG!)\n";
    long long big_mul_ll = 100000LL * 100000LL;
    std::cout << "100000LL * 100000LL     = " << big_mul_ll << " (correct)\n";

    return 0;
}

INT_MAX = 2147483647
naive_mul(INT_MAX, 2) = -2 (UB!)
safe_mul: overflow detected
safe_mul(3,4) = 12
u = 0, u - 1 = 4294967295 (wrap to UINT_MAX)
255 + 1 (unsigned char) = 0 (wrap to 0)
LLONG_MAX + 1 overflow
2^100 = 1267650600228229401496703205376
2^60  = 1152921504606846976
prod  = 1267650600228229401496703205376
mulmod(1000000000, 1000000000, 1000000007) = 49
mulmod_safe = 49
100000 * 100000 (int)   = 1410065408 (WRONG!)
100000LL * 100000LL     = 10000000000 (correct)