Cpp-algorithms/big_integer.cpp at master · SpeedOfMagic/Cpp-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87


struct BigInteger {
	const int b = 1000000000;
	vector<int> dig = {0};

	BigInteger() {}
	BigInteger(vector<int> a) {
		dig = a;
		if (dig.empty() || dig.back() != 0)
			dig.push_back(0);
	}
	BigInteger(int a) {
		dig.clear();
		while (a) {
			dig.push_back(a % b);
			a /= b;
		}
		dig.push_back(0);
	}

	void operator=(BigInteger a)  { dig = a.dig; }

	BigInteger operator+(const BigInteger& other) const {
		vector<int> ans = dig;
		bool carry = false;
		for (size_t i = 0; i < other.dig.size(); i++) {
			if (i == ans.size()) {
                ans.push_back(0);
            }
			if (carry) {
                ++ans[i];
            }

			carry = ans[i] + other.dig[i] >= b;
			ans[i] = (ans[i] + other.dig[i]) % b;
		}
		if (carry)
			ans.push_back(1);
		return BigInteger(ans);
	}

	BigInteger operator*(const BigInteger& a) const {
		vector<int> ans = vector<int>(a.dig.size() + dig.size(), 0);
		for (size_t i = 0; i < dig.size(); i++)
			for (size_t j = 0; j < a.dig.size(); j++)
				ans[i + j] += dig[i] * a.dig[j];

		int carry = 0;
		for (size_t i = 0; i < ans.size(); i++) {
			ans[i] += carry;
			carry = ans[i] / b;
			ans[i] %= b;
		}
		assert(carry == 0);
		while (ans.size() >= 2 && ans.back() == 0 && ans[ans.size() - 2] == 0)
			ans.pop_back();
		return ans;
	}

	bool operator<(const BigInteger& a) const {
		if (a.dig.size() < dig.size())
			return 0;
		else if (dig.size() < a.dig.size())
			return 1;
		for (int i = dig.size() - 1; i >= 0; i--)
			if (dig[i] > a.dig[i])
				return 0;
			else if (dig[i] < a.dig[i])
				return 1;
		return 0;
	}

    friend ostream& operator<<(ostream& o, const BigInteger& num) {
        bool leading_zeroes = true;
        for (auto it = num.dig.rbegin(); it != num.dig.rend(); ++it) {
            if ((*it) != 0) {
                leading_zeroes = false;
            }
            if (leading_zeroes && (*it) == 0) {
                continue;
            }
            o << (*it);
        }
        return o;
    }
};