手写 C++ 高精度

huzixiao · 2025-04-12 15:07:03 · 算法·理论

代码

namespace BigInt {
    using namespace std;
    class INT {
    private:
        int a[10005]; // 倒序高精度数组
        int len; // 高精数字位数（长度）
        bool f = false; // 负数标记（0 为正，1 为负）
        void copy(int a[]) { // 将倒序数组 a 正序存储到正序数组 n 中
            memset(n, 0, sizeof n);
            for (int lena = len, lenn = 1; lena >= 1; lena--, lenn++)
                n[lenn] = a[lena];
        }
    public:
        int n[10005]; // 正序高精度数组
        friend INT Iabs(INT a);
        INT(long long x = 0) { // 构造函数（整型转高精）
            f = false;
            if (x < 0) f = true, x = -x;
            memset(a, 0, sizeof a);
            if (x == 0) {
                len = 1;
            } else {
                for (len = 1; x; len++) a[len] = x % 10, x /= 10;
                len--;
            }
            copy(a);
        }
        INT(string s) { // 构造函数（字符串转高精）
            f = false;
            if (s[0] == '-') f = true, s.erase(0, 1);
            memset(a, 0, sizeof a);
            if (s.empty()) {
                len = 1;
            } else {
                for (len = 1; !s.empty(); len++) {
                    a[len] = s[s.size() - 1] - '0';
                    s.erase(s.size() - 1, 1);
                }
                len--;
            }
            copy(a);
        }
        inline int size() { return len; } // 获取数字位数
        bool operator >(INT b) { // 大于号重载
            if (f && !b.f) return false;
            if (!f && b.f) return true;
            if (!f) {
                if (len != b.len) return len > b.len;
                for (int i = len; i >= 1; i--)
                    if (a[i] != b.a[i])
                        return a[i] > b.a[i];
                return false;
            } else {
                INT a = Iabs(*this);
                b = Iabs(b);
                if (a.len != b.len) return a.len < b.len;
                for (int i = a.len; i >= 1; i--)
                    if (a.a[i] != b.a[i])
                        return a.a[i] < b.a[i];
                return false;
            }
        }
        bool operator ==(INT b) { // 等于号重载
            if ((f && !b.f) || (!f && b.f) || len != b.len)
                return false;
            for (int i = 1; i <= len; i++)
                if (a[i] != b.a[i])
                    return false;
            return true;
        }
        bool operator <(INT b) { return !(*this > b) && !(*this == b); } // 小于号重载
        bool operator >=(INT b) { return (*this > b) || (*this == b); } // 大于等于重载
        bool operator <=(INT b) { return (*this < b) || (*this == b); } // 小于等于重载
        bool operator !=(INT b) { return !(*this == b); } // 不等于重载
        INT operator -() { // 负号重载
            INT b = *this;
            b.f = !b.f;
            return b;
        }
        INT operator +(INT b) { // 高精度加法
            INT a = *this, c;
            if (a.f == b.f) {
                c.f = a.f, a = Iabs(a), b = Iabs(b);
            } else {
                if (Iabs(a) > Iabs(b)) c = Iabs(a) - Iabs(b), c.f = a.f;
                else if (Iabs(b) > Iabs(a)) c = Iabs(b) - Iabs(a), c.f = b.f;
                else return 0;
                return c;
            }
            c.len = max(a.len, b.len) + 1;
            for (int i = 1; i <= c.len; i++) c.a[i] = a.a[i] + b.a[i];
            for (int i = 1; i <= c.len; i++)
                if (c.a[i] >= 10)
                    c.a[i + 1]++, c.a[i] -= 10;
            while (!c.a[c.len] && c.len > 1) c.len--;
            c.copy(c.a);
            return c;
        }
        INT operator -(INT b) { // 高精度减法
            INT a = *this, c;
            if (a.f == true || b.f == true) return c = a + (-b);
            if (a < b) {
                INT t = a;
                a = b, b = t, c.f = true;
            }
            c.len = max(a.len, b.len);
            for (int i = 1; i <= c.len; i++) c.a[i] = a.a[i] - b.a[i];
            for (int i = 1; i <= c.len; i++)
                if (c.a[i] < 0)
                    c.a[i + 1]--, c.a[i] += 10;
            while (!c.a[c.len] && c.len > 1) c.len--;
            c.copy(c.a);
            return c;
        }
        INT operator *(INT b) { // 高精度乘法
            INT a = *this, c;
            a = Iabs(a), b = Iabs(b);
            if (a.f != b.f) c.f = true;
            c.len = a.len + b.len;
            for (int i = 1; i <= a.len; i++)
                for (int j = 1; j <= b.len; j++)
                    c.a[i + j - 1] += a.a[i] * b.a[j];
            for (int i = 1; i <= c.len; i++)
                if (c.a[i] >= 10)
                    c.a[i + 1] += c.a[i] / 10, c.a[i] %= 10;
            while (!c.a[c.len] && c.len > 1) c.len--;
            c.copy(c.a);
            return c;
        }
        INT operator /(int b) { // 高精度除法
            INT a = *this, c;
            if (a.f) c.f = b > 0;
            else c.f = b < 0;
            a = Iabs(a), b = abs(b);
            int x = 0;
            for (int i = a.len; i >= 1; i--) {
                int cur = x * 10 + a.a[i];
                c.a[i] = cur / b;
                x = cur % b;
            }
            c.len = a.len;
            while (c.len > 1 && c.a[c.len] == 0) c.len--;
            c.copy(c.a);
            return c;
        }
        int operator %(int b) { // 取余
            INT a = *this;
            int x = 0, f = (a.f ? -1 : 1);
            a = Iabs(a), b = abs(b);
            for (int i = len; i >= 1; i--)
                x = (x * 10 + a.a[i]) % b;
            return x * f;
        }
        void operator +=(INT b) { *this = *this + b; }
        void operator -=(INT b) { *this = *this - b; }
        void operator *=(INT b) { *this = *this * b; }
        void operator /=(int b) { *this = *this / b; }
        void operator %=(int b) { *this = *this % b; }
        void operator ++() { *this += 1; }
        void operator --() { *this -= 1; }
        void read() { // 读入字符串为高精数字
            string s;
            cin >> s;
            *this = INT(s);
        }
        void print() { // 输出高精数字
            if (f && n[1] != 0) printf("-");
            for (int i = 1; i <= len; i++) printf("%d", n[i]);
        }
    };
    struct INTgreater { // 倒序排序规则
        bool operator ()(INT a, INT b) { return a > b; }
    };
    int INTcint(INT a) {
        int res = 0;
        for (int i = 1; i <= a.size(); i++)
            res = res * 10 + a.n[i];
        if (a < 0) res = -res;
        return res;
    }
    INT Iabs(INT a) { return (a < 0 ? -a : a); } // 绝对值
    INT INTpower(INT a, INT b) { // 幂运算
        INT ans = 1;
        while (b != 0) {
            if (b % 2 == 1) ans = ans * a;
            b = b / 2;
            a = a * a;
        }
        return ans;
    }
}