BigIntMultiply.cpp

#include <vector>
#include <string>
#include <iostream>
#include <cassert>
using namespace std;

/*
BigInt multiply. Use uchar array to store the binary representation.
1. It should be unsigned char (not char);
2. Use carry, and do multiply/add iteratively, this could avoid overflow;
3. .end() is not a valid postion in array, don't visit it directly
4. You can use pop_back() to remove the last one;
*/
class BigInt
{
public:
    int Radix; // 2^8 = 256
    BigInt(const string& s)
    {
        Radix = 1 << 8;
        // for simplicity, lets assume it's less than long
        long value = 0;
        for (int i = 0; i < s.length(); i++)
        {
            value = value * 10 + (s[i] - '0');
        }
        while (value != 0)
        {
            elems.push_back(value % Radix);
            value = value / Radix;
        }
        if (elems.size() == 0)
            elems.push_back(0);
    }

    vector<unsigned char> elems;

    BigInt multiply(const BigInt& b)
    {
        const BigInt& a = *this;
        BigInt c("0");
        c.elems.resize(a.elems.size() + b.elems.size());

        for (int i = 0; i < (int)a.elems.size(); i++)
        {
            int carry = 0;
            for (int j = 0; j < (int)b.elems.size(); j++)
            {
                int total = (int)a.elems[i] * (int)b.elems[j] + c.elems[i + j] + carry;
                c.elems[i + j] = total % Radix;
                carry = total / Radix;
            }
            c.elems[i + b.elems.size()] = carry;
        }
        while (c.elems.size() > 1 && c.elems[c.elems.size() - 1] == 0)
            c.elems.pop_back();
        return c;
    }

    long toValue()
    {
        long value = 0;
        for (int i = elems.size() - 1; i >= 0; i--)
        {
            value = value * Radix + elems[i];
        }
        return value;
    }
};

void test(string a, string b, int c)
{
    BigInt x(a);
    BigInt y(b);
    BigInt z = x.multiply(b);
    assert(z.toValue() == c);
}

int main()
{
    test("256", "2", 512);
    test("2", "256", 512);
    test("0", "0", 0);
    test("34456", "321", 11060376);
    test("112", "4567", 511504);
    test("256", "2", 512);
    test("21", "32", 672);
    test("77777", "1", 77777);

    return 0;
}