I just want to share something to community, after I found this problem in the problemset (which the answer cannot be display as long long integer). Here is my class to calculate on strings (including add, substract, multiply, divide (as two strings), modulo and take gcd, I will add bitwise operators later if possible).
Hope you will find it useful. If you find this incomplete, I would love to read any feedback.
Code
class STRO
{
public:
bool bigger(string a, string b) // check if a is strictly bigger than b or not
{
if (a.length() > b.length()) return true;
if (a.length() < b.length()) return false;
for(int i = 0; i < a.length(); i++)
{
if (a[i] > b[i]) return true;
else if (a[i] < b[i]) return false;
}
return false;
}
string add(string str1, string str2) // add strings, took this from geekforgeeks
{
if (str1.length() > str2.length())
swap(str1, str2);
string str = "";
int n1 = str1.length(), n2 = str2.length();
int diff = n2 - n1;
int carry = 0;
for (int i=n1-1; i>=0; i--)
{
int sum = ((str1[i]-'0') + (str2[i+diff]-'0') + carry);
str.push_back(sum%10 + '0');
carry = sum/10;
}
for (int i=n2-n1-1; i>=0; i--)
{
int sum = ((str2[i]-'0')+carry);
str.push_back(sum%10 + '0');
carry = sum/10;
}
if (carry) str.push_back(carry+'0');
reverse(str.begin(), str.end());
while(str.size() > 1 && str[0] == '0') str.erase(0, 1);
return str;
}
string sub(string str1, string str2) // substract strings, also from geekforgeeks
{
if (bigger(str2, str1)) swap(str1, str2);
string str = "";
int n1 = str1.length(), n2 = str2.length();
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0;
for (int i = 0; i < n2; i++)
{
int sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
for (int i = n2; i < n1; i++)
{
int sub = ((str1[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
reverse(str.begin(), str.end());
while (str.size() > 1 && str[0] == '0') str.erase(0, 1);
return str;
}
string mul(string A, string B) // multiply strings
{
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
string C;
C.resize(A.length() + B.length(),'0');
for (int i = 0; i < A.length(); i++)
{
int c = 0;
FOR(j, 0, B.length()-1)
{
c += ((A[i] - '0') * (B[j] - '0') + C[i + j] - '0');
C[i + j] = (char)(c%10 + '0');
c/=10;
}
if (c > 0) C[i + B.length()] += c;
}
reverse(C.begin(),C.end());
while (C.size() > 1 && C[0] == '0') C.erase(0, 1);
return C;
}
string div(string number, ll divisor) // divide 1 string with 1 number, the version for divide two strings in down below
{
string ans = "";
ll idx = 0;
ll temp = number[idx] - '0';
while (temp < divisor) temp = temp * 10 + (number[++idx] - '0');
while (number.size() > idx)
{
ans += (temp / divisor) + '0';
temp = (temp % divisor) * 10 + number[++idx] - '0';
}
while (ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
if (ans.length() == 0) return "0";
return ans;
}
bool bigger2(string a, string b) // check if a >= b, not strictly greater
{
if (a.length() > b.length()) return true;
if (a.length() < b.length()) return false;
FOR(i, 0, a.length() - 1)
{
if (a[i] > b[i]) return true;
else if (a[i] < b[i]) return false;
}
return true;
}
string dv(string a, string b) // divide as two strings, use binary search
{
if (bigger(b, a)) return "0";
if (a == "0") return "0";
string l = "0";
string r = a;
string mid, mid2;
while (bigger2(r, l))
{
mid = add(r, l);
if ((mid[mid.length() - 1] - '0') % 2 == 1) mid[mid.length() - 1]--;
mid = div(mid, 2);
if (mid == "0") break;
mid2 = mul(mid, b);
if (bigger(mid2, a)) r = sub(mid, "1");
else l = add(mid, "1");
}
return r;
}
string md(string a, string b) // find a % b
{
if (bigger(b, a)) return a;
if (a == "0") return "0";
if (b == "1") return "0";
string l = "0";
string r = a;
string mid, mid2;
while (bigger2(r, l))
{
if (mid == "0") break;
mid = add(r, l);
if ((mid[mid.length() - 1] - '0') % 2 == 1) mid[mid.length() - 1]--;
mid = div(mid, 2);
mid2 = mul(mid, b);
if (bigger(mid2, a)) r = sub(mid, "1");
else l = add(mid, "1");
}
mid = mul(r, b);
mid = sub(a, mid);
while (mid.size() > 1 && mid[0] == '0') mid.erase(0, 1);
if (mid == b) return "0";
return mid;
}
string strgcd(string a, string b) // find gcd(a, b)
{
if (a == "0") return b;
return strgcd(md(b, a), a);
}
};
STRO STR;
Hope you will find this helpful ^_^ Thanks for reading.
this looks decent, but there's a better way of implementing bigint: splitting the digits into a group of, say, 10 digits or 20 digits, each group then can be displayed as an integer, operations will be faster and much simpler to store (which is how many bigint templates are implemented)