目录
加法高精度
两个正整数相加
两个正小数相加
两正数相加
减法高精度
两个正整数相减
两个正小数相减
两正数相减
加减法总结
乘法高精度
两个正整数相乘
两个正小数相乘
乘法总结
加法高精度
题目来源洛谷：P1601 A+B Problem（高精）
高精度：顾名思义，就是在很大的位数情况下进行运算，其基本思想就是用数组进行模拟加法进位，最后遍历数组输出。可以看到提示的a，b最大值达到10^18，而内置类型long long能接受数据的最大值在10^19，题目目的就是为了不让你内置类型来接收数据。
两个正整数相加
我们可以使用字符串来模拟高精度运算，本题要求很少：只需要正整数相加即可，以 83 + 2047 为例模拟一下加法过程，我们可以看一下下图：
按照加法原则，个位与个位相加，十位与十位相加……注意相加的过程中要加上前一位的进位，注意最高位相加后要看进位d是否为0，代码如下：
// 整数部分 // 全是正数
string add_int(string a, string b)
{
string ret; //存放最终结果
int d = 0;// 记录进位
int na = a.size(), nb = b.size();
int n = max(na, nb);// 统一个数
// 位数不够前面补0
if (na > nb)
for (int i = 1; i <= na - nb; i++)
b = "0" + b;
else
for (int i = 1; i <= nb - na; i++)
a = "0" + a;
for (int i = n - 1; i >= 0; i--)
{
int tmp = 0, tmp_a = a[i] - '0', tmp_b = b[i] - '0';
tmp = tmp_a + tmp_b + d; //加前一次的进位
d = tmp / 10;
tmp %= 10;
ret.push_back(tmp + '0');
}
if (d != 0)
ret.push_back(d + '0');
reverse(ret.begin(), ret.end());
return ret;
}两个正小数相加
根据此题，我又试着把大于0的小数相加设计了出来，这样使得原本加法更加完善，可以对大于等于0的所有数进行加法运算，但是需要注意一点的是，小数部分靠近小数点的为高位，意味着我们要在数字后面补0，以 0.99 和 0.4721 为例子，看以下图示：
根据上图可以用代码将其实现：
// 小数部分 // 全是正数
string add_float(string a, string b)
{
string ret;
int d = 0;// 记录进位
int na = a.size(), nb = b.size();
int n = max(na, nb);// 统一个数
// 位数不够后面补0
if (na > nb)
for (int i = 1; i <= na - nb; i++)
b = b + "0";
else
for (int i = 1; i <= nb - na; i++)
a = a + "0";
for (int i = n - 1; i >= 0; i--)
{
int tmp = 0, tmp_a = a[i] - '0', tmp_b = b[i] - '0';
tmp = tmp_a + tmp_b + d; //加前一次的进位
d = tmp / 10;
tmp %= 10;
ret.push_back(tmp + '0');
}
if (d != 0)// 说明要进位到整数
ret.push_back('x');
reverse(ret.begin(), ret.end());//前导x说明要整数部分+1
return ret;
}两正数相加
通过上述两个函数合并可以试着实现正数的加法，这里说一下我的思路：
- 找到两个字符串中的小数点
- 将字符串分为两个子串：左半部分为正整数子串，右半部分为正小数子串
- 两个部分分别调用上述函数
- 结果合并成一个字符串，该字符串为最终结果
为了提高代码的可读性，本蒟蒻在每行代码后面添加了注释，大家可以试着看一下：
bz：本人考虑到小数部分相加刚好为1的情况，那么可以试着不要后面一大串全是0的子串，直接输出整数部分即可，这样更加贴合大家生活中的加法习惯。以下为代码：
// 加法
string add(string a,string b)
{
auto it_a = a.find('.'), it_b = b.find('.');
string a_int = a, b_int = b, a_float, b_float; // 默认a b是整数
if (it_a != -1)// 找到小数点了就要分成两部分
{
a_int = a.substr(0, it_a); // 把整数部分裁下来
a_float = a.substr(it_a + 1, a.size() - it_a); // 把小数部分裁下来
}
if(it_b != -1)
{
b_int = b.substr(0, it_b);
b_float = b.substr(it_b + 1, b.size() - it_b); // 同上
}
string ad_float = add_float(a_float, b_float);
if (ad_float[0] == 'x')//看看有没有前导x，有就需要进位
{
ad_float = ad_float.substr(1, ad_float.size() - 1); //把前导x舍弃
a_int = add_int(a_int, "1"); // 小数进位只会加1
}
int count = 0;
for (auto e : ad_float) // 看看结尾是不是全是0
if (e == '0')
count++;
if (count == ad_float.size()) // 说明全是0，ret可以不要了
ad_float.clear(); //清空
string ad_int = add_int(a_int, b_int);
string ret = ad_int;
if (ad_float.size() != 0) // 说明里面有小数
ret = ret + "." + ad_float;
return ret;
}减法高精度
减法高精度与加法高精度略有不同，其区别在于进位，加法的进位是把进位值给高一级位，而减法进位需要向高一级位借一位（前数比后数小的前提下）
两个正整数相减
减法的难点在于：它不像加法那样可以一位一位顺位相加，在借位的情况下，可能出现越位减一的情况，例如100 - 9，要从百位借位，这样大大增加了难度。
注意以下两个特殊情况：
- 两个相同数相减为0
- 低位数不够，向高位借1
根据加法的代码，可以考虑在加法的基础上进行修改，并且通过两个正整数的相减可以实现一正一负的加法运算，提高了代码的复用性。看以下一下代码：
// 整数部分 // 全是正数 // 大 - 小
string sub_int(string a, string b)
{
string ret; // 存放最终结果
int d = 0;// 记录进位
int na = a.size(), nb = b.size();
int n = max(na, nb);// 统一个数
// 位数不够前面补0
if (na > nb)
for (int i = 1; i <= na - nb; i++)
b = "0" + b;
else
for (int i = 1; i <= nb - na; i++)
a = "0" + a;
string maxn = a, minn = b; // 重新搞两个字符串（提高可读性）
for (int i = n - 1; i >= 0; i--)
{
int tmp = 0, tmp_max = maxn[i] - '0' + d, tmp_min = minn[i] - '0'; // 进位放初始化
d = 0;// 注意用完 d 归零
if (tmp_max < tmp_min) // 借位情况（大数该位不够减小数该位）
{
tmp_max += 10; //问前面一位要了一个1
d = -1;
}
tmp = tmp_max - tmp_min;
ret.push_back(tmp + '0');
}
for (int i = n - 1; i >= 1; i--) //一样的数相减全是0删掉（注意留最后一个0）
{
if (ret[i] == '0')
ret.pop_back();
else
break;
}
reverse(ret.begin(), ret.end());
return ret;
}
两个正小数相减
正小数相减和相加类似，最后返回的字符串如果要借个位的一位就存放一个x，两函数合并时判断是否有x（需要向个位借一位的情况）即可，代码如下：
// 小数部分 // 全是正数 // 大 - 小
string sub_float(string a, string b)
{
string ret; // 存放最终结果
int d = 0;// 记录进位
int na = a.size(), nb = b.size();
int n = max(na, nb);// 统一个数
// 位数不够后面补0
if (na > nb)
for (int i = 1; i <= na - nb; i++)
b = b + "0";
else
for (int i = 1; i <= nb - na; i++)
a = a + "0";
string maxn = a, minn = b; // 重新搞两个字符串（提高可读性）
for (int i = n - 1; i >= 0; i--)
{
int tmp = 0, tmp_max = maxn[i] - '0' + d, tmp_min = minn[i] - '0'; // 进位放初始化
d = 0;// 注意用完 d 归零
if (tmp_max < tmp_min) // 借位情况（大数该位不够减小数该位）
{
tmp_max += 10; //问前面一位要了一个1
d = -1;
}
tmp = tmp_max - tmp_min;
ret.push_back(tmp + '0');
}
if (d == -1)// 整数部分也要减1
ret.push_back('x');
reverse(ret.begin(), ret.end());
return ret;
}两正数相减
与加法相同，裁剪小数和整数两部分字符串依次调用各自的函数即可，代码如下：
// 减法 // 默认 大 - 小
string sub(string a, string b)
{
auto it_a = a.find('.'), it_b = b.find('.');
string a_int = a, b_int = b, a_float, b_float; // 默认a b是整数
if (it_a != -1)// 找到小数点了就要分成两部分
{
a_int = a.substr(0, it_a); // 把整数部分裁下来
a_float = a.substr(it_a + 1, a.size() - it_a); // 把小数部分裁下来
}
if (it_b != -1)
{
b_int = b.substr(0, it_b);
b_float = b.substr(it_b + 1, b.size() - it_b); // 同上
}
string su_float = sub_float(a_float, b_float);
if (su_float[0] == 'x')//看看有没有前导x，有就需要借位
{
su_float = su_float.substr(1, su_float.size() - 1); //把前导x舍弃
a_int = sub_int(a_int, "1"); // 小数进位只会加1
}
int count = 0;
for (auto e : su_float) // 看看结尾是不是全是0
if (e == '0')
count++;
if (count == su_float.size()) // 说明全是0，ret可以不要了
su_float.clear(); //清空
string su_int = sub_int(a_int, b_int);
string ret = su_int;
if (su_float.size() != 0) // 说明里面有小数
ret = ret + "." + su_float;
return ret;
}加减法总结
通过减法可以利用该函数实现加法中的正数加负数，当然在面对小减大的情况时，需要通过一个比较函数来判断两数的绝对值大小，处理完之和直接在最终结果的字符串前头插一个” - " 即可，加减法无非以下几种情况：
加减法所有可能情况
式子形式 大小比较 结果大小 正数a + 正数b 两者都大于0 大于0 正数a + 负数b | a | >= | b | 大于等于0 正数a + 负数b | a | < | b | 小于0 负数a + 负数b 两者都小于0 小于0 正数a - 正数b
| a | >= | b | 大于等于0 正数a - 负数b a >= 0 b < 0 大于0 负数a - 正数b a < 0 b >= 0 小于0 负数a - 负数b | a | >= | b | 小于0 负数a - 负数b
| a | < | b | 大于0
以下代码为绝对值化处理和比较函数的内容，大家可以根据本蒟蒻上述代码尝试其他情况的代码编写。
// 绝对值化
if (a[0] == '-')
a = a.substr(1, a.size() - 1);
if (b[0] == '-')
b = b.substr(1, b.size() - 1);
// 比较函数
bool my_cmp(string a, string b) // 补0 且 绝对值化后进行比较
{
// 默认 a > b
for (int i = 0; i < a.size(); i++)
if (a[i] < b[i])
return false;
return true;
}乘法高精度
本题来自洛谷题库：P1303 A*B Problem，相比加减法的高精度，乘法的高精度相对麻烦一些，但是归根结底还是运用字符串来实现位数的变化，其主要区别在于进位，加减法的进位只会是1，但是乘法的进位可以达到8（9 * 9 = 81），本文不探讨除法的高精度，个人认为除法的高精度不常见，接下来我们试着解决上题。
注意特殊情况：0和任何数相乘都为0！！！
两个正整数相乘
以 679 x 58 为例，看以下图片如何模拟该乘法过程：
可以看到乘法内部实际为多个加法操作的求和，我们可以在上面的加法操作上进行修改：
// 整数部分 // 全是正数
string mul_int(string a, string b)
{
if (a == "0" || b == "0")//处理特例
return "0";
string ret = "0"; // 存放最终结果
int d = 0;// 记录进位
string longer = a, shorter = b; // 假设法
if (a.size() < b.size())
swap(longer, shorter);
int n = shorter.size(); // 乘的次数
reverse(longer.begin(), longer.end()); reverse(shorter.begin(), shorter.end()); //逆置后位数顺序
for (int i = 0; i < n; i++)
{
string str; // 临时存放数据
for (int j = 0; j < longer.size(); j++)
{
int tmp = 0, tmp_longer = longer[j] - '0', tmp_shorter = shorter[i] - '0';
tmp = tmp_longer * tmp_shorter + d; //加上进位
d = tmp / 10;
tmp %= 10;
str.push_back(tmp + '0');
}
if (d != 0) //比原数多一位
str.push_back(d + '0');
reverse(str.begin(), str.end());
for (int z = 1; z <= i; z++) // 从十位开始就要后面补0
str.push_back('0');
ret = add_int(ret, str);// 调用上述两整数相加运算
d = 0; // 用完复位
}
return ret;
}
两个正小数相乘
小数相乘可以利用上面的正整数相乘，回想一下小学时期如何解决小数相乘问题的？
本蒟蒻总结了以下几个步骤：
- 计算两数小数点后几位之和
- 小数前面的0全部去掉
- 整数相乘
- 添加小数点
光看文字可能有些抽象，我们来看图片：
根据上面图片是不是思路更加清晰了呢？下面我们来实现代码操作：
// 小数部分 // 全是正数
string mul(string a, string b)
{
if (a == "0" || b == "0")//处理特例
return "0";
auto it_a = a.find('.'), it_b = b.find('.');
string a_int = a, b_int = b, a_float, b_float; // 默认a b是整数
if (it_a != -1)// 找到小数点了就要分成两部分
{
a_int = a.substr(0, it_a); // 把整数部分裁下来
a_float = a.substr(it_a + 1, a.size() - it_a); // 把小数部分裁下来
}
if (it_b != -1)
{
b_int = b.substr(0, it_b);
b_float = b.substr(it_b + 1, b.size() - it_b); // 同上
}
int n = a_float.size() + b_float.size();
if (a_int == "0")
a_int.clear();
if (b_int == "0")
b_int.clear();
a = a_int + a_float, b = b_int + b_float; // 拼起来
string ret = mul_int(a, b); int nret = ret.size();
if (n >= nret)// 不够还要补0
{
//为什么不用insert？ 如果要头插大量0，insert时间复杂度太高
reverse(ret.begin(), ret.end()); //逆置尾插0
for (int i = 0; i <= n - nret; i++)
ret.push_back('0');
ret.insert(n, 1, '.'); //这里的insert只要挪一个0就行 好好思考为什么
reverse(ret.begin(), ret.end());
}
else
ret.insert(nret - n, 1, '.');
return ret;
}上述代码我将含有小数和整数的数字合并在一起，该函数可以处理各种正数相乘。
乘法总结
乘法一共有以下几种情况，需要注意以下两点：
- 两个小数相乘不会向整数位进位
- 0乘任何数都为0
乘法需要考虑以下所有情况：
乘法所有可能情况
式子形式 大小比较 结果大小 0 x 任何数 0 正数a x 正数b 两者都大于0 大于0 正数a x 负数b a > 0 b < 0 小于0 负数a x 负数b a < 0 b < 0 大于0 整数a x 小数b 两者都大于0（相当于除法） 大于0 小数a x 小数b 两者都大于0 大于0且小于1
最后附上以上的测试代码，供大家调试：
int main()
{
string sa, sb, ans; cin >> sa >> sb;
//ans = add_int(sa, sb);
//ans = add_float(sa, sb);
//ans = add(sa, sb);
//ans = sub_int(sa, sb);
//ans = sub_float(sa, sb);
//ans = sub(sa, sb);
//ans = mul_int(sa, sb);
ans = mul(sa, sb);
cout << ans << endl;
return 0;
}
