大整形(BigInteger)类实现，原生高效高精度运算，oj效率极高，支持正负数

时间：2021-01-16 22:14:42 阅读：44 评论：0 收藏：0 [点我收藏+]

众所周知，数与数进行运算时，当两个数位数过大，我们的程序就会出错。所以我们就出现了高精度运算，本类的本质原理是采用无符号短整形数组存储数的每一位（采用char数组存取可优化空间复杂度，但处理过程麻烦）进行一些基本的高精度运算，部分优化实现参考了STL部分容器底层操作，但本类没有使用除string之外任何STL封装容器，性能值得保障（string类的使用是为了方便转换和构造操作，去除没有任何影响），可适用于oj大部分高精度运算题（本人亲测效率较高，目前未出现TL）。

??类的接口如下

??构造函数支持无参构造（默认为0），支持最大long long整形，char*字符串和string类字符串的有参构造和拷贝构造。

BigInteger(long long n = 0);

BigInteger(const string& str);

BigInteger(const char* str);

BigInteger(const BigInteger& bi);

??重载了等于号拷贝构造

BigInteger& operator=(const BigInteger& bi);

??实现基本加减乘除取余操作并返回自身引用（这里类似于复合赋值运算，即this+=bi，oj建议使用，可提高效率，少一次拷贝构造）；同时对于高精度除低精度我额外重载了相应三个函数以提高效率（divideAndRemainder，divide，mod），在某些情况下可优先使用；divideAndRemainder独立函数返回值为一个长度为二BigInteger数组（请用BigInteger*接收，不用释放，内部有完美释放内存机制，不会造成内存泄漏），下标为一的为除数，下标为二的为余数，对于oj某些特定要求题目可休先考虑使用。

BigInteger& add(const BigInteger& bi);

BigInteger& subtract(const BigInteger& bi);

BigInteger& multiply(const BigInteger& bi);

BigInteger& divide(const BigInteger& bi);

BigInteger& mod(const BigInteger& bi);

BigInteger* divideAndRemainder(const BigInteger& bi);

BigInteger& divide(const long long li);

BigInteger& mod(const long long li);

BigInteger* divideAndRemainder(const long long li);

??重载了复合赋值操作运算符

BigInteger& operator+=(const BigInteger& bi);

BigInteger& operator-=(const BigInteger& bi);

BigInteger& operator*=(const BigInteger& bi);

BigInteger& operator/=(const BigInteger& bi);

BigInteger& operator%=(const long long li);

BigInteger& operator%=(const BigInteger& bi);

BigInteger& operator/=(const long long li);

??重载了自增自减（this++，++this，this--，--this）运算符

BigInteger& operator++();

BigInteger operator++(int t);

BigInteger& operator--();

BigInteger operator--(int t);

??重载了强转运算符（(long long)this，(string)this），string强转不建议使用（方便写代码的时候可使用），建议使用toString函数（string强转会多调用一直拷贝构造函数，降低效率，而toString只调用一次拷贝构造函数，效率较高）

operator long long();

operator string();

??重载了加减乘除取余操作和比较操作运算符，以及取负运算符

friend BigInteger& operator-(BigInteger& bi);

friend BigInteger operator+(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator-(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator*(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator/(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator%(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator>(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator<(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator>=(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator<=(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator==(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator!=(const BigInteger& bi_a, const BigInteger& bi_b);

friend BigInteger operator/(const BigInteger& bi_a, const long long li_b);

friend BigInteger operator%(const BigInteger& bi_a, const long long li_b);

??重载了输入输出流操作运算符，但是为了效率，内部采用的时c语言scanf和printf实现的，没有采用流读入和输出，读者可看情况修改。

friend istream& operator>>(istream& _cin, BigInteger& bi);

friend ostream& operator<<(ostream& _cout, const BigInteger& bi);

??重载了下标访问运算符，类似于数组，可实现访问和修改大整形类中索引为index的值，如：1234567，访问 => this[0] = 1，this[1] = 2，修改 => this[4] = 5 结果为 1235567，切勿修改超过10，否则运算将全部发生错误；切勿将最高位修改为0，否则输出错误（对此情况读者可以重写函数做预处理，本人未作多余处理）。

unsigned short& operator[](size_t index);

??获取对象的整形形式，如果操过了long long的范围将返回0，否则返回正常的数

long long toInteger() const;

??获取对象的string类字符串形式

string toString() const;

??获取对象大整形数长度

size_t length() const;

??获取内部存储大整形数数组最大可用空间

size_t size() const;

??对象自身和另一个对象的比较函数（即比较两个大整形数），小于返回-1，等于返回0，大于返回1

int compare(const BigInteger& bi) const;

??交换两个大整形数

void swap(BigInteger& bi);

??大整形数清0（注意：不是清空，和STL其他容器的clear不同，此为清0）

void clear();

??重新设置当前大整形数对象内部存储大整形数数组最大可用空间

void resize(size_t size);

??设置大整形数对象初始空间大小（注意：不是明面上的意思，它设置的是输入流输入时临时输入char*存储数组的大小，方便处理，不易溢出），如果你的构造对象时为有参构造，不需输入则可不使用，默认内部大小为100010。

void setInitSize(size_t initsize);

??设置大整形数的正负，传入true设置为正数，否则为负数，为零时设置无效

void setpositive(bool flag);

??弹出大整形数的最高位，仅在数位大于一的情况下

void pop();

??放入一个数（不超过10，否则运算错误，不为0，否则无效）作为大整数新的最高位。（如：1234，this.push(9) => 91234）

void push(const unsigned short num);

class BigInteger {
   public:
    BigInteger(long long n = 0);
    BigInteger(const string& str);
    BigInteger(const char* str);
    BigInteger(const BigInteger& bi);
    ~BigInteger();

    BigInteger& operator=(const BigInteger& bi);

    BigInteger& add(const BigInteger& bi);
    BigInteger& subtract(const BigInteger& bi);
    BigInteger& multiply(const BigInteger& bi);
    BigInteger& divide(const BigInteger& bi);
    BigInteger& mod(const BigInteger& bi);
    BigInteger* divideAndRemainder(const BigInteger& bi);
    BigInteger& divide(const long long li);
    BigInteger& mod(const long long li);
    BigInteger* divideAndRemainder(const long long li);

    BigInteger& operator+=(const BigInteger& bi);
    BigInteger& operator-=(const BigInteger& bi);
    BigInteger& operator*=(const BigInteger& bi);
    BigInteger& operator/=(const BigInteger& bi);
    BigInteger& operator%=(const long long li);
    BigInteger& operator%=(const BigInteger& bi);
    BigInteger& operator/=(const long long li);

    BigInteger& operator++();
    BigInteger operator++(int t);
    BigInteger& operator--();
    BigInteger operator--(int t);

    operator long long();
    operator string();

    friend BigInteger& operator-(BigInteger& bi);
    friend BigInteger operator+(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator-(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator*(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator/(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator%(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator>(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator<(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator>=(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator<=(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator==(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator!=(const BigInteger& bi_a, const BigInteger& bi_b);
    friend BigInteger operator/(const BigInteger& bi_a, const long long li_b);
    friend BigInteger operator%(const BigInteger& bi_a, const long long li_b);

    friend istream& operator>>(istream& _cin, BigInteger& bi);
    friend ostream& operator<<(ostream& _cout, const BigInteger& bi);

    unsigned short& operator[](size_t index);

    long long toInteger() const;
    string toString() const;
    size_t length() const;
    size_t size() const;
    int compare(const BigInteger& bi) const;
    void swap(BigInteger& bi);
    void clear();
    void resize(size_t size);
    void setInitSize(size_t initsize);
    void setpositive(bool flag);
    void pop();
    void push(const unsigned short num);

   private:
    unsigned short* __num = NULL;
    size_t __num_length = 0, __num_size = 0, __init_size = 1e5 + 10;
    bool __flag = true;

    BigInteger** __new_bi_location = NULL;
    size_t __new_bi_location_length = 0, __new_bi_location_size = 0;

    void __location_push_back(BigInteger* new_bi_location);

    size_t __newsize(unsigned short*& num, size_t length);
    size_t __resize(unsigned short*& num, size_t length, size_t prelen);

    void __add(const BigInteger& a, const BigInteger& b, BigInteger& c);
    void __subtract(const BigInteger& a, const BigInteger& b, BigInteger& c);
    void __multiply(const BigInteger& a, const BigInteger& b, BigInteger& c);
    void __divide_mod_bi(const BigInteger& a, const BigInteger& b, BigInteger& divider, BigInteger& remainder);
    void __divide_mod_li(const BigInteger& a, const long long b, BigInteger& divider, BigInteger& remainder);
};

??具体实现如下

BigInteger::BigInteger(long long n) {
    this->__num_size = this->__newsize(this->__num, 20);
    if (!n) {
        this->__flag = true;
        this->__num[this->__num_length++] = 0;
    } else {
        if (n < 0) {
            this->__flag = false;
            n = -n;
        } else
            this->__flag = true;
        while (n) {
            this->__num[this->__num_length++] = n % 10;
            n /= 10;
        }
    }
}

BigInteger::BigInteger(const string& str) {
    int start_index = 0, str_length = str.length();
    if (str[0] == ‘-‘) {
        this->__flag = false;
        start_index++;
    }

    while (str[start_index] == ‘0‘)
        start_index++;

    this->__num_size = this->__newsize(this->__num, str_length - start_index + 1);

    for (int i = str_length - 1; i >= start_index; i--)
        this->__num[this->__num_length++] = str[i] - ‘0‘;

    if (!this->__num_length)
        this->__num[this->__num_length++] = 0;
}

BigInteger::BigInteger(const char* str) {
    int start_index = 0, str_length = strlen(str);
    if (str[0] == ‘-‘) {
        this->__flag = false;
        start_index++;
    }

    while (str[start_index] == ‘0‘)
        start_index++;

    this->__num_size = this->__newsize(this->__num, str_length - start_index + 1);

    for (int i = str_length - 1; i >= start_index; i--)
        this->__num[this->__num_length++] = str[i] - ‘0‘;

    if (!this->__num_length)
        this->__num[this->__num_length++] = 0;
}

BigInteger::BigInteger(const BigInteger& bi) {
    this->__num_size = this->__newsize(this->__num, bi.__num_size);
    memcpy(this->__num, bi.__num, bi.__num_length * sizeof(unsigned short));
    this->__num_length = bi.__num_length;
    this->__flag = bi.__flag;
}

BigInteger::~BigInteger() {
    delete[] this->__num;
    for (size_t i = 0; i < this->__new_bi_location_length; i++)
        delete[] this->__new_bi_location[i];
    delete[] this->__new_bi_location;
}

BigInteger& BigInteger::operator=(const BigInteger& bi) {
    this->__num_size = this->__newsize(this->__num, bi.__num_size);
    memcpy(this->__num, bi.__num, bi.__num_length * sizeof(unsigned short));
    this->__num_length = bi.__num_length;
    this->__flag = bi.__flag;
    return *this;
}

BigInteger& operator-(BigInteger& bi) {
    bi.__flag = !bi.__flag;
    return bi;
}

BigInteger& BigInteger::add(const BigInteger& bi) {
    if (bi.__flag == this->__flag)
        this->__add(*this, bi, *this);
    else if (bi.__flag) {
        this->__flag = true;
        this->swap(BigInteger(bi).subtract(*this));
    } else {
        BigInteger& bi_map = const_cast<BigInteger&>(bi);
        bi_map.__flag = true;
        this->subtract(bi_map);
        bi_map.__flag = false;
    }
    return *this;
}

BigInteger& BigInteger::subtract(const BigInteger& bi) {
    if (bi.__flag == this->__flag) {
        int _cmp = this->compare(bi);
        if (_cmp > 0) {
            if (this->__flag)
                this->__subtract(*this, bi, *this);
            else
                this->__subtract(bi, *this, *this);
            this->__flag = true;
        } else if (_cmp < 0) {
            if (this->__flag)
                this->__subtract(bi, *this, *this);
            else
                this->__subtract(*this, bi, *this);
            this->__flag = false;
        } else
            this->clear();
    } else
        this->__add(*this, bi, *this);
    return *this;
}

BigInteger& BigInteger::multiply(const BigInteger& bi) {
    if (this->__num_length == 1 && this->__num[0] == 0 || bi.__num_length == 1 && bi.__num[0] == 0)
        this->clear();
    else if (this->__num_length == 1 && this->__num[0] == 1) {
        bool this_flag = this->__flag;
        BigInteger ans(bi);
        this->swap(ans);
        this->__flag = bi.__flag ? this_flag : !this_flag;
    } else if (bi.__num_length == 1 && bi.__num[0] == 1) {
        this->__flag = bi.__flag ? this->__flag : !this->__flag;
        return *this;
    } else {
        bool this_flag = this->__flag;
        this->__multiply(*this, bi, *this);
        this->__flag = this_flag != bi.__flag ? false : true;
    }
    return *this;
}

BigInteger& BigInteger::divide(const BigInteger& bi) {
    if (bi.__num_length == 1 && bi.__num[0] == 1)
        this->__flag = bi.__flag == this->__flag;
    else
        this->swap(this->divideAndRemainder(bi)[0]);
    return *this;
}

BigInteger& BigInteger::mod(const BigInteger& bi) {
    if (bi.__num_length == 1 && bi.__num[0] == 1)
        this->clear();
    else
        this->swap(this->divideAndRemainder(bi)[1]);
    return *this;
}

BigInteger* BigInteger::divideAndRemainder(const BigInteger& bi) {
    BigInteger* ans = new BigInteger[2];
    this->__location_push_back(ans);

    if (bi.__num_length == 1 && bi.__num[0] == 0)
        abort();

    if (bi.__num_length == 1 && bi.__num[0] == 1) {
        BigInteger temp(*this);
        ans[0].swap(temp);
        ans[0].__flag = bi.__flag == this->__flag;
    } else {
        bool this_flag = this->__flag;
        if (bi.__flag != this->__flag)
            this->__flag = bi.__flag;
        int _cmp = this->compare(bi);
        if (_cmp > 0) {
            if (bi.__flag) {
                this->__divide_mod_bi(*this, bi, ans[0], ans[1]);
                ans[0].__flag = this_flag == bi.__flag;
                ans[1].__flag = this_flag;
            } else {
                BigInteger temp(*this);
                ans[1].swap(temp);
            }
        } else if (_cmp < 0) {
            if (bi.__flag) {
                BigInteger temp(*this);
                ans[1].swap(temp);
            } else {
                this->__divide_mod_bi(*this, bi, ans[0], ans[1]);
                ans[0].__flag = this_flag == bi.__flag;
                ans[1].__flag = this_flag;
            }
        } else
            ans[0] = this_flag == bi.__flag ? 1 : -1;
        this->__flag = this_flag;
    }
    return ans;
}

BigInteger& BigInteger::divide(const long long li) {
    if (li == 1 || li == -1)
        this->__flag = li > 0 ? this->__flag : !this->__flag;
    else
        this->swap(this->divideAndRemainder(li)[0]);
    return *this;
}

BigInteger& BigInteger::mod(const long long li) {
    if (li == 1 || li == -1)
        this->clear();
    else
        this->swap(this->divideAndRemainder(li)[1]);
    return *this;
}

BigInteger* BigInteger::divideAndRemainder(const long long li) {
    BigInteger* ans = new BigInteger[2];
    this->__location_push_back(ans);

    if (li == 0)
        abort();

    bool li_flag = li > 0;
    if (li == 1 || li == -1) {
        BigInteger temp(*this);
        ans[0].swap(temp);
        ans[0].__flag = li_flag == this->__flag;
    } else {
        BigInteger bi(li);
        if (bi.length() > 18)
            this->__divide_mod_bi(*this, bi, ans[0], ans[1]);
        else
            this->__divide_mod_li(*this, (li > 0 ? li : -li), ans[0], ans[1]);
        ans[0].__flag = this->__flag == li_flag;
        ans[1].__flag = this->__flag;
    }
    return ans;
}

BigInteger& BigInteger::operator+=(const BigInteger& bi) {
    this->add(bi);
    return *this;
}

BigInteger& BigInteger::operator-=(const BigInteger& bi) {
    this->subtract(bi);
    return *this;
}

BigInteger& BigInteger::operator*=(const BigInteger& bi) {
    this->multiply(bi);
    return *this;
}

BigInteger& BigInteger::operator/=(const BigInteger& bi) {
    this->divide(bi);
    return *this;
}

BigInteger& BigInteger::operator%=(const BigInteger& bi) {
    this->mod(bi);
    return *this;
}

BigInteger& BigInteger::operator/=(const long long li) {
    this->divide(li);
    return *this;
}

BigInteger& BigInteger::operator%=(const long long li) {
    this->mod(li);
    return *this;
}

BigInteger& BigInteger::operator++() {
    this->__add(*this, 1, *this);
    return *this;
}

BigInteger BigInteger::operator++(int t) {
    BigInteger ans(*this);
    this->__add(*this, 1, *this);
    return *this;
}

BigInteger& BigInteger::operator--() {
    this->__subtract(*this, 1, *this);
    return *this;
}

BigInteger BigInteger::operator--(int t) {
    BigInteger ans(*this);
    this->__subtract(*this, 1, *this);
    return *this;
}

BigInteger::operator long long() {
    return this->toInteger();
}

BigInteger::operator string() {
    return this->toString();
}

BigInteger operator+(const BigInteger& bi_a, const BigInteger& bi_b) {
    BigInteger ans(bi_a);
    ans.add(bi_b);
    return ans;
}

BigInteger operator-(const BigInteger& bi_a, const BigInteger& bi_b) {
    BigInteger ans(bi_a);
    ans.subtract(bi_b);
    return ans;
}

BigInteger operator*(const BigInteger& bi_a, const BigInteger& bi_b) {
    BigInteger ans(bi_a);
    ans.multiply(bi_b);
    return ans;
}

BigInteger operator/(const BigInteger& bi_a, const BigInteger& bi_b) {
    BigInteger ans(bi_a);
    ans.divide(bi_b);
    return ans;
}

BigInteger operator%(const BigInteger& bi_a, const BigInteger& bi_b) {
    BigInteger ans(bi_a);
    ans.mod(bi_b);
    return ans;
}

BigInteger operator>(const BigInteger& bi_a, const BigInteger& bi_b) {
    return bi_a.compare(bi_b) > 0;
}

BigInteger operator<(const BigInteger& bi_a, const BigInteger& bi_b) {
    return bi_a.compare(bi_b) < 0;
}

BigInteger operator>=(const BigInteger& bi_a, const BigInteger& bi_b) {
    int _cmp = bi_a.compare(bi_b);
    return (_cmp == 1 || _cmp == 0);
}

BigInteger operator<=(const BigInteger& bi_a, const BigInteger& bi_b) {
    int _cmp = bi_a.compare(bi_b);
    return (_cmp == -1 || _cmp == 0);
}

BigInteger operator==(const BigInteger& bi_a, const BigInteger& bi_b) {
    return bi_a.compare(bi_b) == 0;
}

BigInteger operator!=(const BigInteger& bi_a, const BigInteger& bi_b) {
    return !(bi_a.compare(bi_b) == 0);
}

BigInteger operator/(const BigInteger& bi_a, const long long li_b) {
    BigInteger ans(bi_a);
    ans.divide(li_b);
    return ans;
}

BigInteger operator%(const BigInteger& bi_a, const long long li_b) {
    BigInteger ans(bi_a);
    ans.mod(li_b);
    return ans;
}

istream& operator>>(istream& _cin, BigInteger& bi) {
    char* str = new char[bi.__init_size];
    scanf("%s", str);
    int start_index = 0, str_length = strlen(str);

    if (str[0] == ‘-‘) {
        bi.__flag = false;
        start_index++;
    }

    while (str[start_index] == ‘0‘)
        start_index++;

    if (bi.__num_size < str_length - start_index + 1)
        bi.__num_size = bi.__newsize(bi.__num, str_length - start_index + 1);
    bi.__num_length = 0;

    for (int i = str_length - 1; i >= start_index; i--)
        bi.__num[bi.__num_length++] = str[i] - ‘0‘;

    if (!bi.__num_length)
        bi.__num[bi.__num_length++] = 0;

    delete[] str;
    return _cin;
}

ostream& operator<<(ostream& _cout, const BigInteger& bi) {
    if (!bi.__flag)
        putchar(‘-‘);
    for (int i = bi.__num_length - 1; i >= 0; i--)
        printf("%hd", bi.__num[i]);
    return _cout;
}

unsigned short& BigInteger::operator[](size_t index) {
    return this->__num[index];
}

long long BigInteger::toInteger() const {
    if (this->__num_length < 19 || (this->__num_length == 19 && (this->__flag ? this->compare(BigInteger(9223372036854775807LL)) <= 0 : this->compare(BigInteger("-9223372036854775807")) >= 0))) {
        long long ans = 0, cnt = 1;
        for (int i = 0; i < this->__num_length; i++, cnt *= 10)
            ans += cnt * this->__num[i];
        return this->__flag ? ans : -ans;
    } else
        return 0LL;
}

string BigInteger::toString() const {
    string ans;
    if (!this->__flag)
        ans.push_back(‘-‘);
    for (int i = this->__num_length - 1; i >= 0; i--)
        ans.push_back(this->__num[i] + ‘0‘);
    return ans;
}

size_t BigInteger::length() const {
    return this->__num_length;
}

size_t BigInteger::size() const {
    return this->__num_size;
}

void BigInteger::pop() {
    if (this->__num_length > 1)
        this->__num_length--;
}

void BigInteger::push(const unsigned short num) {
    if (this->__num_length == 1 && this->__num[0] == 0)
        this->__num_length--;
    if (this->__num_length >= this->__num_size) {
        this->__num_size = (size_t)(this->__num_size * 1.5);
        this->__num_size = this->__resize(this->__num, this->__num_size == 1 ? 2 : this->__num_size, this->__num_length);
    }
    if (num)
        this->__num[this->__num_length++] = num;
}

int BigInteger::compare(const BigInteger& bi) const {
    if (this->__flag != bi.__flag)
        return this->__flag ? 1 : -1;
    else {
        int ans = this->__flag ? 1 : -1;
        if (this->__num_length > bi.__num_length)
            return ans;
        else if (this->__num_length < bi.__num_length)
            return -ans;
        else {
            for (int i = this->__num_length - 1; i >= 0; i--)
                if (this->__num[i] < bi.__num[i])
                    return -ans;
                else if (this->__num[i] > bi.__num[i])
                    return ans;
            return 0;
        }
    }
}

void BigInteger::swap(BigInteger& bi) {
    std::swap(this->__flag, bi.__flag);
    std::swap(this->__num_size, bi.__num_size);
    std::swap(this->__num_length, bi.__num_length);
    std::swap(this->__num, bi.__num);
    std::swap(this->__new_bi_location_size, bi.__new_bi_location_size);
    std::swap(this->__new_bi_location_length, bi.__new_bi_location_length);
    std::swap(this->__new_bi_location, bi.__new_bi_location);
}

void BigInteger::clear() {
    this->__num_length = 1;
    this->__num[0] = 0;
    this->__flag = true;
}

void BigInteger::resize(size_t size) {
    this->__num_size = this->__resize(this->__num, size, this->__num_size);
}

void BigInteger::setInitSize(size_t initsize) {
    if (this->__num_length == 1 && this->__num[0] == 0)
        return;
    this->__init_size = initsize;
}

void BigInteger::setpositive(bool flag) {
    this->__flag = flag;
}

void BigInteger::__location_push_back(BigInteger* new_bi_location) {
    if (this->__new_bi_location_length >= this->__new_bi_location_size) {
        this->__new_bi_location_size *= 1.5;
        this->__new_bi_location_size = this->__new_bi_location_size ? this->__new_bi_location_size : 4;
        BigInteger** new_bi_location_list = new BigInteger* [this->__new_bi_location_size] { NULL };
        memcpy(new_bi_location_list, this->__new_bi_location, this->__new_bi_location_length * sizeof(BigInteger*));
        free(this->__new_bi_location);
        this->__new_bi_location = new_bi_location_list;
    }
    this->__new_bi_location[this->__new_bi_location_length++] = new_bi_location;
}

size_t BigInteger::__newsize(unsigned short*& num, size_t length) {
    delete[] num;
    num = new unsigned short[length]{0};
    return length;
}

size_t BigInteger::__resize(unsigned short*& num, size_t length, size_t prelen) {
    unsigned short* new_num = new unsigned short[length]{0};
    memcpy(new_num, num, (prelen > length ? length : prelen) * sizeof(unsigned short));
    delete[] num;
    num = new_num;
    return length;
}

void BigInteger::__add(const BigInteger& a, const BigInteger& b, BigInteger& c) {
    int a_length = a.__num_length, b_length = b.__num_length;
    int min_length = a_length < b_length ? (b_length + 1 > c.__num_size ? (c.__num_size = this->__resize(c.__num, b_length + 1, c.__num_length)) : 0, a_length)
                                         : (a_length + 1 > c.__num_size ? (c.__num_size = this->__resize(c.__num, a_length + 1, c.__num_length)) : 0, b_length);
    c.__num_length = 0;
    unsigned short sum, t = 0;
    for (int i = 0; i < min_length; i++) {
        sum = a.__num[i] + b.__num[i] + t;
        t = sum / 10;
        c.__num[c.__num_length++] = sum % 10;
    }
    if (a_length > b_length) {
        for (int i = min_length; i < a_length; i++) {
            sum = a.__num[i] + t;
            t = sum / 10;
            c.__num[c.__num_length++] = sum % 10;
        }
    } else if (a_length < b_length) {
        for (int i = min_length; i < b_length; i++) {
            sum = b.__num[i] + t;
            t = sum / 10;
            c.__num[c.__num_length++] = sum % 10;
        }
    }
    if (t)
        c.__num[c.__num_length++] = t;
}

void BigInteger::__subtract(const BigInteger& a, const BigInteger& b, BigInteger& c) {
    int a_length = a.__num_length, b_length = b.__num_length;
    if (c.__num_size < a_length)
        c.__num_size = this->__resize(c.__num, a_length, c.__num_size);
    c.__num_length = 0;
    short sum, t = 0;
    for (int i = 0; i < b_length; i++) {
        sum = a.__num[i] - b.__num[i] - t;
        t = 0;
        c.__num[c.__num_length++] = sum >= 0 ? sum : (t = 1, sum + 10);
    }
    if (a_length != b_length) {
        for (int i = b_length; i < a_length; i++) {
            sum = a.__num[i] - t;
            t = 0;
            c.__num[c.__num_length++] = sum >= 0 ? sum : (t = 1, sum + 10);
        }
    }
    while (c.__num_length > 1 && c.__num[c.__num_length - 1] == 0) c.__num_length--;
}

void BigInteger::__multiply(const BigInteger& a, const BigInteger& b, BigInteger& c) {
    int a_length = a.__num_length, b_length = b.__num_length;
    BigInteger ans;
    ans.__num_size = this->__newsize(ans.__num, a_length + b_length + 1);
    ans.__num_length = a_length + b_length;
    unsigned short t;
    for (int i = 0; i < a_length; i++) {
        t = 0;
        for (int j = 0; j < b_length; j++) {
            ans.__num[i + j] = a.__num[i] * b.__num[j] + ans.__num[i + j] + t;
            t = ans.__num[i + j] / 10;
            ans.__num[i + j] %= 10;
        }
        ans.__num[b_length + i] = t;
    }
    while (ans.__num_length > 1 && ans.__num[ans.__num_length - 1] == 0) ans.__num_length--;
    this->swap(ans);
}

void BigInteger::__divide_mod_bi(const BigInteger& a, const BigInteger& b, BigInteger& divider, BigInteger& remainder) {
    BigInteger temp, cp_a(a);
    temp.__num_size = this->__newsize(temp.__num, a.__num_length + b.__num_length + 1);
    remainder.swap(cp_a);
    temp.__flag = remainder.__flag = true;

    size_t prelen = divider.__num_length;
    divider.__num_length = a.__num_length - b.__num_length + 1;

    if (divider.__num_length > divider.__num_size)
        divider.__num_size = this->__resize(divider.__num, divider.__num_length + 1, prelen);

    for (int i = divider.__num_length - 1; i >= 0; i--) {
        memset(temp.__num, 0, sizeof(i + b.__num_length));
        for (size_t j = 0; j < b.__num_length; j++)
            temp.__num[j + i] = b.__num[j];
        temp.__num_length = b.__num_length + i;
        while (remainder.compare(temp) >= 0) {
            divider.__num[i]++;
            this->__subtract(remainder, temp, remainder);
        }
    }
    while (divider.__num_length > 1 && divider.__num[divider.__num_length - 1] == 0)
        divider.__num_length--;
}

void BigInteger::__divide_mod_li(const BigInteger& a, const long long b, BigInteger& divider, BigInteger& remainder) {
    long long t = 0;
    divider.__num_length = a.__num_length;
    divider.__num_size = this->__newsize(divider.__num, divider.__num_length + 1);
    for (int i = divider.__num_length - 1; i >= 0; i--) {
        divider.__num[i] = (t * 10 + a.__num[i]) / b;
        t = (t * 10 + a.__num[i]) % b;
    }
    while (divider.__num_length > 1 && divider.__num[divider.__num_length - 1] == 0)
        divider.__num_length--;
    BigInteger ans(t);
    remainder.swap(ans);
}

本类为作者原创，如有差错，请指正，源码没有原理介绍和注释，请谅解。

大整形(BigInteger)类实现，原生高效高精度运算，oj效率极高，支持正负数

原文：https://www.cnblogs.com/dreamy-xay/p/14286875.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)