big_integer.cpp

#include"big_integer.h"

long long MAX = 1LL << 32;

big_integer::big_integer() {
    elements.push_back(0);
    elements.push_back(0);
}

big_integer::big_integer(big_integer const& other) {
    elements = other.elements;
}

big_integer::big_integer(int a) {
    bool f = a < 0;
    if (f) {
        a = -a;
    }
    elements.push_back(a);
    elements.push_back(0);
    if (f) {
        elements = (-*this).elements;
    }
    deletezeros();
}

void big_integer::deletezeros() {
    if (elements.size() == 0) {
        elements.push_back(0);
        elements.push_back(0);
        return;
    }
    unsigned back = elements.back();
    while (elements.size() > 0 && elements.back() == back) {
        elements.pop_back();
    }
    elements.push_back(back);
    elements.push_back(back);
}

big_integer::big_integer(std::string const& str) {
    std::string s = str;
    if (s.length() == 0) {
        elements.push_back(0);
        elements.push_back(0);
        return;
    }
    unsigned sign;
    if (s[0] == '-') {
        sign = MAX - 1;
        s = s.substr(1, s.length() - 1);
    } else {
        sign = 0;
    }
    std::reverse(s.begin(), s.end());
    for (int i = 0; i < s.length(); i++) {
        s[i] -= '0';
    }
    int len = s.length();
    int j = 0;
    unsigned cur = 0;
    while (len > 0) {
        cur += unsigned(s[0] % 2) >> j;
        if (j == 31) {
            j = 0;
            elements.push_back(cur);
            cur = 0;
        }
        for (int i = 0; i < len; i++) {
            if (s[i] % 2 == 1 && i != 0) {
                s[i - 1] += 5;
            }
            s[i] /= 2;
        }
        while (len > 0 && s[len - 1] == 0) {
            len--;
        }
        j++;
    }
    elements.push_back(0);
    if (sign == MAX - 1) {
        elements = (-*this).elements;
    }
    deletezeros();
}

big_integer big_integer::operator+() const {
    return big_integer(*this);
}

big_integer big_integer::operator-() const {
    big_integer temp = big_integer(*this);
    for (int i = 0; i < elements.size(); i++) {
        temp.elements[i] ^= MAX - 1;
    }
    long long carry = MAX - 1;
    for (int i = 0; i < temp.elements.size(); i++) {
        long long cur = carry + temp.elements[i];
        carry = cur / MAX;
        temp.elements[i] = cur % MAX;
    }
    return temp;
}

big_integer big_integer::operator~() const {
    big_integer temp = big_integer(*this);
    for (int i = 0; i < elements.size(); i++) {
        temp.elements[i] ^= MAX - 1;
    }
    return temp;
}

int big_integer::get_bit(int i) const {
    if (i < elements.size()) {
        return (elements[i / 32] >> (i % 32)) % 2;
    }
    if (elements.back() == 0) {
        return 0;
    }
    return 1;
}

unsigned big_integer::get_word(int i) const {
    if (i < elements.size()) {
        return elements[i];
    } else {
        return elements.back();
    }
}

bool operator == (const big_integer &l, const big_integer &r) {
    for (int i = 0; i < std::max(l.elements.size(), r.elements.size()); i++) {
        if (l.get_word(i) != r.get_word(i)) {
            return false;
        }
    }
    return true;
}

bool operator < (const big_integer &l, const big_integer &r) {
    int lsign = l.elements.back();
    int rsign = r.elements.back();
    if (lsign > rsign) {
        return true;
    }
    if (lsign < rsign) {
        return false;
    }
    for (int i = std::max(l.elements.size(), r.elements.size()); i >= 0; i--) {
        if (l.get_word(i) < r.get_word(i)) {
            return true;
        }
        if (l.get_word(i) > r.get_word(i)) {
            return false;
        }
    }
    return false;
}

bool operator > (const big_integer &l, const big_integer &r) {
    return r < l;
}

bool operator <= (const big_integer &l, const big_integer &r) {
    return !(l > r);
}

bool operator >= (const big_integer &l, const big_integer &r) {
    return !(l < r);
}

bool operator != (const big_integer &l, const big_integer &r) {
    return !(l == r);
}

big_integer operator + (const big_integer &l, const big_integer &r) {
    std::vector<unsigned> res(std::max(l.elements.size(), r.elements.size()) + 2);
    long long c = 0;
    for (int i = 0; i < res.size(); i++) {
        long long temp = l.get_word(i) + r.get_word(i) + c;
        c = temp / MAX;
        res[i] = temp % MAX;
    }
    if (l.elements.back() == MAX - 1) {
        if (r.elements.back() == MAX - 1) {
            res[res.size() - 1] = MAX - 1;
        } else if (-l > r) {
            res[res.size() - 1] = MAX - 1;
        }
    } else {
        if (r.elements.back() == MAX - 1 && (-r > l)) {
            res[res.size() - 1] = MAX - 1;
        }
    }
    big_integer ans;
    ans.elements = res;
    ans.deletezeros();
    return ans;
}

big_integer& big_integer::operator+=(big_integer const& r) {
    big_integer temp = *this + r;
    *this = temp;
    return *this;
}

big_integer operator - (const big_integer &l, const big_integer &r) {
    return l + (-r);
}

big_integer& big_integer::operator-=(big_integer const& r) {
    big_integer temp = *this - r;
    *this = temp;
    return *this;
}

big_integer& big_integer::operator++() {
    big_integer temp = *this;
    *this += 1;
    return temp;
}

big_integer big_integer::operator++(int) {
    *this += 1;
    return *this;
}

big_integer& big_integer::operator--() {
    big_integer temp = *this;
    *this -= 1;
    return temp;
}

big_integer big_integer::operator--(int) {
    *this -= 1;
    return *this;
}

big_integer operator&(big_integer const& a, big_integer const& b) {
    std::vector<unsigned> c(std::max(a.elements.size(), b.elements.size()));
    for (int i = 0; i < c.size(); i++) {
        c[i] = a.get_word(i) & b.get_word(i);
    }
    big_integer res;
    res.elements = c;
    res.deletezeros();
    return res;
}

big_integer operator|(big_integer const& a, big_integer const& b) {
    std::vector<unsigned> c(std::max(a.elements.size(), b.elements.size()));
    for (int i = 0; i < c.size(); i++) {
        c[i] = a.get_word(i) | b.get_word(i);
    }
    big_integer res;
    res.elements = c;
    res.deletezeros();
    return res;
}

big_integer operator^(big_integer const& a, big_integer const& b) {
    std::vector<unsigned> c(std::max(a.elements.size(), b.elements.size()));
    for (int i = 0; i < c.size(); i++) {
        c[i] = a.get_word(i) ^ b.get_word(i);
    }
    big_integer res;
    res.elements = c;
    res.deletezeros();
    return res;
}

big_integer operator<<(big_integer const& a, int b) {
    std::vector<unsigned> c(a.elements.size() * 32 + b);
    for (int i = 0; i < a.elements.size(); i++) {
        c[i + b] = a.get_bit(i);
    }
    std::vector<unsigned> d(a.elements.size() + b);
    long long cur = 0;
    for (int i = 0; i < c.size(); i+=32) {
        for (int j = 0; j < 32; j++) {
            d[i / 32] += c[i + j] << j;
        }
    }
    big_integer res;
    res.elements = d;
    res.deletezeros();
    return res;
}

big_integer operator>>(big_integer const& a, int b) {
    int temp = a.elements.size();
    if (temp * 32 <= b) {
        return big_integer();
    }
    std::vector<unsigned> c(temp * 32 - b);
    for (int i = b; i < temp; i++) {
        c[i - b] = a.get_bit(i);
    }
    std::vector<unsigned> d(temp - b);
    long long cur = 0;
    for (int i = 0; i < c.size(); i+=32) {
        for (int j = 0; j < 32; j++) {
            d[i / 32] += c[i + j] << j;
        }
    }
    big_integer res;
    res.elements = d;
    res.deletezeros();
    return res;
}

big_integer& big_integer::operator&=(big_integer const& r) {
    big_integer temp = *this & r;
    *this = temp;
    return *this;
}

big_integer& big_integer::operator|=(big_integer const& r) {
    big_integer temp = *this | r;
    *this = temp;
    return *this;
}

big_integer& big_integer::operator^=(big_integer const& r) {
    big_integer temp = *this ^ r;
    *this = temp;
    return *this;
}

big_integer& big_integer::operator<<=(int r) {
    big_integer temp = *this << r;
    *this = temp;
    return *this;
}

big_integer& big_integer::operator>>=(int r) {
    big_integer temp = *this >> r;
    *this = temp;
    return *this;
}

big_integer operator * (const big_integer &l, const big_integer &r) {
    bool f = l.elements.back() ^ r.elements.back();
    big_integer a = l;
    big_integer b = r;
    if (l.elements.back() == MAX - 1) {
        a = -a;
    }
    if (r.elements.back() == MAX - 1) {
        b = -b;
    }
    std::vector<unsigned> c(a.elements.size() + b.elements.size() + 3);
    for (int i = 0; i < a.elements.size(); i++) {
        unsigned long long carry = 0;
        for (int j = 0; j < b.elements.size() || carry; j++) {
            unsigned long long cur = c[i + j] + a.get_word(i) * b.get_word(j) + carry;
            c[i + j] = cur % MAX;
            carry = cur / MAX;
        }
    }
    c.push_back(0);
    big_integer ans;
    ans.elements = c;
    if (f) {
        ans = -ans;
    }
    ans.deletezeros();
    return ans;
}

big_integer& big_integer::operator*=(big_integer const& r) {
    big_integer temp = *this * r;
    *this = temp;
    return *this;
}

big_integer operator/(big_integer const& l, big_integer const& r) {
    big_integer a = l;
    big_integer b = r;
    bool f = l.elements.back() ^ r.elements.back();
    if (l.elements.back() == 1) {
        a = -a;
    }
    if (r.elements.back() == 1) {
        b = -b;
    }
    std::vector<unsigned> res(a.elements.size());
    big_integer c;
    for (int i = a.elements.size() - 1; i >= 0; i--) {
        c <<= 32;
        c.elements[0] = a.get_word(i);
        long long l = 0;
        long long r = MAX;
        while (l < r - 1) {
            long long m = (l + r) / 2;
            if (m * b <= c) {
                l = m;
            } else {
                r = m;
            }
        }
        res[i] = l;
        c -= b * l;
    }
    c.elements = res;
    c.deletezeros();
    if (f) {
        c = -c;
    }
    return c;
}

big_integer operator%(big_integer const& a, big_integer const& b) {
    return a - (a / b) * b;
}

big_integer& big_integer::operator/=(big_integer const& r) {
    big_integer temp = *this / r;
    *this = temp;
    return *this;
}

big_integer& big_integer::operator%=(big_integer const& r) {
    big_integer temp = *this % r;
    *this = temp;
    return *this;
}

std::string to_string(big_integer const& a) {
    big_integer x = a;
    std::string BIG, degree2;
    BIG.resize(a.elements.size() + 2);
    degree2.resize(a.elements.size() + 2);
    degree2[0] = 1;
    bool f = (x.elements.back() == MAX - 1);
    if (f) {
        x = -x;
    }
    for (int i = 0; i < x.elements.size(); i++) {
        if (x.get_bit(i) == 1) {
            int carry = 0;
            for (int j = 0; j < BIG.size() - 1; j++) {
                int cur = carry + BIG[j] + degree2[j];
                carry = cur / 10;
                BIG[j] = cur % 10;
            }
            BIG[BIG.size() - 1] = carry;
        }
        int carry = 0;
        for (int j = 0; j < degree2.size() - 1; j++) {
            int cur = carry + degree2[j] * 2;
            carry = cur / 10;
            degree2[j] = cur % 10;
        }
        degree2[degree2.size() - 1] = carry;
    }
    while (BIG.size() > 0 && BIG[BIG.size() - 1] == 0) {
        BIG.pop_back();
    }
    for (int i = 0; i < BIG.size(); i++) {
        BIG[i] += '0';
    }
    std::reverse(BIG.begin(), BIG.end());
    if (BIG.size() == 0) {
        return "0";
    }
    if (f) {
        BIG = "-" + BIG;
    }
    return BIG;
}