bigint.cpp

#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <cassert>
#include <cmath>

using namespace std;

class BigInt
{
    private:
        /**
         * Always in form:
         * *this <  0: ________ ... 0xffffffff 
         * *this >= 0: ________ ... 0x00000000
         *             ^            ^
         *             |　　　　　 　 +---- Most Significant
         *             +---- Least Significant
         */
        vector<int> m_ints;

        int add(int x, int y, int* carry) const
        {
            int z = x + y + *carry;
            int bitx = ((unsigned int)x & (1 << 31)) >> 31;
            int bity = ((unsigned int)y & (1 << 31)) >> 31;
            int bitz = ((unsigned int)z & (1 << 31)) >> 31;

            if (bitx == 1 && bity == 1) {
                *carry = 1;
            } else if ((bitx ^ bity) == 1 && bitz == 0) {
                *carry = 1;
            } else {
                *carry = 0;
            }

            return z;
        }

    public:
        BigInt(const BigInt&) = default;

        BigInt(int n)
        {
            m_ints.push_back(n);
            if (n > 0) {
                m_ints.push_back(0);
            } else if (n < 0) {
                m_ints.push_back(-1);
            }
        }

        BigInt& operator+=(const BigInt& rhs)
        {
            assert(m_ints.back() == -1 || m_ints.back() == 0);
            assert(rhs.m_ints.back() == -1 || rhs.m_ints.back() == 0);

            auto& l_ints = m_ints;
            const auto& r_ints = (this == &rhs) ? BigInt(rhs).m_ints : rhs.m_ints;

            while(l_ints.size() < r_ints.size()) {
                l_ints.push_back(l_ints.back());
            }

            int i = 0;
            int carry = 0;

            while(i < r_ints.size()) {
                l_ints[i] = add(l_ints[i], r_ints[i], &carry);
                ++i;
            }

            while(i < l_ints.size()) {
                l_ints[i] = add(l_ints[i], r_ints[0], &carry);
                ++i;
            }

            int sign = l_ints.back() >= 0 ? 0 : -1;
            while(l_ints.back() == sign) {
                l_ints.pop_back();
            }
            l_ints.push_back(sign);

            return *this;
        }

        BigInt operator+(const BigInt& rhs) const
        {
            BigInt result = *this;
            result += rhs;
            return result;
        }

        BigInt operator++(int)
        {
            BigInt tmp = *this;
            *this += 1;
            return tmp;
        }

        BigInt& operator++()
        {
            *this += 1;
            return *this;
        }

        BigInt operator-() const
        {
            BigInt result = *this;
            for(int i = 0; i < result.m_ints.size(); ++i) {
                result.m_ints[i] = ~result.m_ints[i];
            }
            result += 1;
            return result;
        }

        BigInt& operator-=(const BigInt& rhs)
        {
            auto toAdd = -rhs;
            *this += toAdd;
            return *this;
        }

        BigInt operator-(const BigInt& rhs) const
        {
            BigInt result = *this;
            result -= rhs;
            return result;
        }

        BigInt& operator--()
        {
            *this -= 1;
            return *this;
        }

        BigInt operator--(int)
        {
            BigInt tmp = *this;
            *this -= 1;
            return tmp;
        }

        bool operator==(const BigInt& rhs) const
        {
            auto result = *this - rhs;
            return result.m_ints.size() == 1 && result.m_ints[0] == 0;
        }

        bool operator!=(const BigInt& rhs) const
        {
            return !(*this == rhs);
        }

        bool operator>(const BigInt& rhs) const
        {
            auto result = *this - rhs;
            return result.m_ints.size() > 1 && result.m_ints.back() == 0;
        }

        bool operator<(const BigInt& rhs) const
        {
            auto result = *this - rhs;
            return result.m_ints.back() == -1;
        }

        BigInt& operator*=(const BigInt& rhs)
        {
            auto count = rhs;
            if (count == 0) {
                *this = 0;
                return *this;
            }

            if (count < 0) {
                count = -count;
                *this = -*this;
            }

            while(count != 0) {
                count--;
                *this += *this;
            }
            return *this;
        }

        string toBitString() const
        {
            stringstream ss;
            vector<char> bits;
            for(int i = 0; i < m_ints.size(); ++i) {
                unsigned int val = m_ints[i];
                for(int shift = 0; shift < 32; ++shift) {
                    bits.push_back((((val & (1 << shift)) >> shift)) == 0 ? '0' : '1');
                }
                bits.push_back('|');
            }
            return string(bits.begin(), bits.end());
        }
};

int main(int argc, char* argv[])
{
    BigInt x = (pow(2,31) - 1);
    BigInt y = 10;
    BigInt z = -1 * pow(2, 15);

    cout << "x: " << x.toBitString() << endl;
    cout << "y: " << y.toBitString() << endl;
    cout << "z: " << z.toBitString() << endl;

    z += y;
    cout << "z: " << z.toBitString() << endl;

    z += z;
    cout << "z: " << z.toBitString() << endl;

    return 0;
}