概述
目录
前言
一、抽象数据类型BigInt
二、辅助方法
1. 加法
对齐
2. 减法
A和B的比较
A和B的交换
3. 乘法
反转
4. 除法
x和B的比较
5. 小结
三、高精度加减乘除类
四、加减乘除的实现
1. 准备工作
打印结果
打印A
打印B
2. 加法实现
3. 减法实现
4. 小结
subtrac(A, B)的实现
5. 乘法实现
6. 除法实现
7. 取余实现
总结
前言
我们常用int类型的变量进行A+B的计算，然而int的最大值为21474836473，很难满足大数据的保存，那long long呢？也不行，它也有范围，再大一些的数据，它也束手无策，为解决高精度问题，我们可以使用数组，数组的每个元素保存A的每位数，这样数据就能存储起来了。
一、抽象数据类型BigInt
我们将数的符号和数据分开存储，符号用字符存储，数据用字符串存储。
class Bigint {
private:
// data存放数据的绝对值 符号存放在sing里
string data;
char sing;
public:
// 初始化
Bigint(char sing, string data) {
this->sing = sing;
this->data = data;
}
string getData() {
return data;
}
char getSing() {
return sing;
}
};二、辅助方法
我们先来明确一下需要实现的方法有哪些，首先肯定有加减乘除以及取余操作， 其次就是更新A和B的方法。为了实现以上操作，我们肯定还需要一些辅助方法，使代码更具可读性。接下来我们一个一个分析：
1. 加法
我们先想一想我们自己计算加法是怎么样的，首先我们会把A和B的个位与个位对齐，十位与十位对齐，完成了对齐之后，我们会让个位相加，如果大于9，就让其进位，只保留个位数，如此循环，便可得到最终答案。
至此，我们已经发现了第一个需要的辅助方法——对齐，接下来我们来实现一下这个方法。
对齐
vector<int> align(vector<int> x) {
int tail = BIT_NUM-1;
int i=0;
while (x[i++] != -1);
int xSize = i - 1;
for (int i=xSize-1; i>=0; i--) {
x[tail] = x[i];
tail--;
}
while (tail) {
x[tail--] = 0;
}
x[tail] = 0;
return x;
}for循环之前，我们先让tail和 i指向正确的位置
为什么有while的条件是x[i++] != -1？我们对数组初始化的时候，将元素都赋值为-1，作判断标记，因此，实际上的数组是这样的
接着让i和tail往前走，把123放到数组右边去
再把原来的123都变为0
对齐操作完成
2. 减法
减法操作和加法差不多，都是先对齐，后计算的，但不同的是，减法必须满足A>B，否则，就要让A，B的值互换后，让大的数作为被减数。
于是，这里便有两个辅助方法了：1. A和B的比较方法； 2. A和B的交换方法
A和B的比较
//比较 若A>=B返回true，否则返回false
bool compare() {
if (preArrSize > nextArrSize) {
return true;
} else if (preArrSize < nextArrSize) {
return false;
} else {
for (int i=0; i<BIT_NUM-1; i++) {
if (preArr[i] > nextArr[i]) {
return true;
} else if (preArr[i] < nextArr[i]) {
return false;
} else {
continue;
}
}
return true;
}
}代码很好理解，A比B长，必然A>B；A比B短，必然A<B；AB等长时，从最高位开始比较，如果for循环结束后没能return出去，说明A=B。
A和B的交换
void subtract() {
if (compare()) result = subtract(A, B);
else result = subtract(B, A);
}
vector<int> subtract(vector<int> A, vector<int> B) {
}我们不能直接修改AB的值，修改AB的操作只能放在更新A和B的值方法上。
因此，我们使用传参的方式来实现AB的互换，如果A>=B，就让A-B，否则，就让B-A。
至于减法的代码，我们放在后面实现。
3. 乘法
看下这个乘法计算过程，我们先让2*4得到8，再让1*4得到4，然后3*2得到6，3*1得到3，这个很容易，但是我们怎么知道，8应该放在个位，而4和6应该放在十位，3放在百位呢？
我们先看8是怎么来的，是A[0]*B[0]吧， 然后放在result[0]的位置，4是A[1]*B[0]，然后放result[1]的位置，6是A[0]*B[1]，放在result[1]的位置，3是A[1]*B[1]，放在result[2]的位置，看出来了吧，是不是有一个关系 result[i+j] = A[i] * B[j]。
那么也能像加法减法那样先对齐，然后这样计算吗，显然不行的，你看上图红色下标的位置，是从右到左递增的，而我们数组的下标是0 1 2这样从左到右递增的，于是，我们需要将AB反转过来。把1 2 变成 2 1，3 4 变成 4 3。
这样，得到的resul反转过来就是计算结果了。
综上所述，我们需要一个辅助函数——反转，来帮我们完成这一步骤。
反转
vector<int> reverse(vector<int> x) {
int l = 0, r = 0;
while (x[r] != -1) {
r++;
}
r--;
while (l < r) {
int t = x[l];
x[l] = x[r];
x[r] = t;
l++;
r--;
}
return x;
}先确定l，r的位置
接下来，对区间[l, r]内的数交换即可。
4. 除法
首先，我们要保证A>=B，否则，结果为0。
我们先让8和33比较，发现8<33，于是得到0，然后让85和33比较，发现85>33，得到2以及余数19，再落下一位7，197和33，得到5以及余数32，7是最后一位了，算法结束。
要完成上述步骤，我们需要一个比较方法，让x和B比较，返回比较结果，要注意的是，这个比较方法不同于我们刚刚实现的方法，我们刚刚实现的方法是只让AB比较，是没有传参的，这个需要传一个参数x。
x和B的比较
//传入x与B比较，大于返回1，等于返回0，小于返回-1，特殊情况x为空时，返回2
int compare(vector<int> x) {
if (x.empty()) {
return 2;
}
int n = x.size();
if (n > nextArrSize) {
return 1;
} else if (n < nextArrSize) {
return -1;
} else {
for (int i=0; i<n; i++) {
if (x[i] > nextArr[i]) {
return 1;
} else if (x[i] < nextArr[i]) {
return -1;
}
}
return 0;
}
}该方法与我们之前实现的比较方法的区别有3点。
一是返回值不再是bool类型，因为该方法有4种情况，bool类型显然难以满足
二是多了一个传参x，因为本方法就是用来比较x和B的，x自然要传进来。
三是要判断x是否为空，至于为什么，后面会说。
5. 小结
以上方法都是辅助方法，均属于private类型，避免用户调用使程序崩溃。在实现加减乘除前，先把它们实现了，会让我们接下来的工作事半功倍。
三、高精度加减乘除类
class addSubtractMultiplyDivide {
private:
char preSing;
//前数符号
vector<int> preArr;
//前数数据
int preArrSize;
//前数数组元素个数
char nextSing;
//后数符号
vector<int> nextArr;
//后数数据
int nextArrSize;
//后数数组元素个数
bool compareRes;
//前数与后数的比较结果，大于等于为true，否则为false
char resSing;
//计算结果数据
vector<int> resArr;
//计算结果符号
vector<int> align(vector<int> x);
//对齐
bool compare();
//比较A和B
int compare(vector<int> x);
//比较x和B
vector<int> reverse(vector<int> x);
//反转x
vector<int> subtract(vector<int> preArr, vector<int> nextArr);
//返回A - B结果
public:
//构造函数 传入两个BigInt，对上面数据初始化
addSubtractMultiplyDivide(Bigint pre, Bigint nex) {
preSing = pre.getSing();
preArr.resize(BIT_NUM, -1);
preArrSize = pre.getData().size();
string preData = pre.getData();
for (int i=0; i<preArrSize; i++) {
preArr[i] = preData[i] - '0';
}
nextSing = nex.getSing();
nextArr.resize(BIT_NUM, -1);
nextArrSize = nex.getData().size();
string nextData = nex.getData();
for (int i=0; i<nextArrSize; i++) {
nextArr[i] = nextData[i] - '0';
}
compareRes = compare();
resArr.resize(BIT_NUM, 0);
}
//加
void add();
//减
void subtract();
//乘
void multiply();
//除
void divide();
//取余
void mod();
//打印结果
void print();
//打印A
void printPre();
//打印B
void printNext();
}四、加减乘除的实现
1. 准备工作
实现加减乘除之前，我们先实现打印函数，分别是打印A的值，B的值以及计算结果result的值，以便于我们debug。
打印结果
void print() {
if (resArr[0] == 0) {
cout << 0 << endl;
return;
}
if (resSing == '-') {
cout << '-';
}
int n = resArr.size();
for (int i=0; i<n; i++) {
cout << resArr[i];
}
cout << endl;
}打印A
void printPre() {
if (preSing == '-') {
cout << preSing;
}
for (int i=0; preArr[i]!=-1; i++) {
cout << preArr[i];
}
cout << endl;
}打印B
void printNext() {
if (nextSing == '-') {
cout << nextSing;
}
for (int i=0; nextArr[i]!=-1; i++) {
cout << nextArr[i];
}
cout << endl;
}2. 加法实现
四步走：
1. 确定符号
当AB异号时，先确定符号，再调用减法函数让绝对值大的减去绝对值小的：
若A是正号，B是负号
当时，例如A = 5，B = -3，result = 2，显然计算结果符号resSing为正号
当时，例如A = 3，B = -5，result = -2，显然计算结果符号resSing为负号
若B是正号，A是负号
当时，例如B = 5，A = -3，result = 2，显然计算结果符号resSing为正号
当时，例如B = 3，A = -5，result = -2，显然计算结果符号resSing为负号
注意：调用减法时，要把绝对值大的放在前边，绝对值小的放在后边。调用完减法接着一定要return出去，不再执行以下步骤。
当AB同号时：
若AB都是正号，计算结果符号resSing为正号
若AB都是负号，计算结果符号resSing为负号
if (preSing == '+' && nextSing == '-') {
if (compareRes) { // |A| >= |B|
resSing = '+';
resArr = subtract(preArr, nextArr);
} else {
// |A| < |B|
resSing = '-';
resArr = subtract(nextArr, preArr);
}
return;
} else if (preSing == '-' && nextSing == '+') {
if (!compareRes) { // |B| > |A|
resSing = '+';
resArr = subtract(nextArr, preArr);
} else {
// |B| <= |A|
resSing = '-';
resArr = subtract(preArr, nextArr);
}
return;
} else if (preSing == '+' && nextSing == '+') {
resSing = '+';
} else {
resSing = '-';
}2. 对齐
vector<int> alignedPre = align(preArr);
vector<int> alignedNext = align(nextArr);3. 从数组尾开始 往前加
resArr.clear();
resArr.resize(BIT_NUM, 0);
for (int i=BIT_NUM-1; i>=0; i--) {
resArr[i] += alignedPre[i] + alignedNext[i];
if (resArr[i] > 9) {
resArr[i-1] = resArr[i] / 10;
resArr[i] = resArr[i] % 10;
}
}4. 整理
如图，计算结果result为003333，我们需要去掉其中的前导0。
vector<int> _res;
int i = 0;
while (resArr[i] == 0) {
i++;
}
int j = i;
while (j != BIT_NUM) {
_res.push_back(resArr[j]);
j++;
}
resArr = _res;3. 减法实现
将减号放进B中，转成加法。
若A为正号，B为负号，例如A = 5，B = -3， 相当于5 + 3 = 8
if (preSing == '+' && nextSing == '-') {
nextSing = '+';
add();
nextSing = '-';
return;
}若A为负号，B为正号，例如A = -5，B = 3， 相当于(-5) + (-3) = -8
if (preSing == '-' && nextSing == '+') {
nextSing = '-';
add();
nextSing = '+';
return;
}若AB都为正号，例如A = 5，B = 3，相当于5 + (-3) = 2
if (preSing == '+' && nextSing == '+') {
nextSing = '-';
add();
nextSing = '+';
return;
}若AB都为负号，例如A = -5， B = -3，相当于(-5) + (3) = -2
if (preSing == '-' && nextSing == '-') {
nextSing = '+';
add();
nextSing = '-';
return;
}注意：修改完符号调用完加法后记得修改回来
4. 小结
看到这里，你可能有以下问题：
1. 前面写辅助函数时，写的减法为什么就直接减，而这里的减法实现却是转为加法呢？
2. 这里加法的实现，异号时调用了加法；减法的实现，都要调用加法。这样做不会反复调用，无限循环吗？
我们写辅助函数时，是认为AB都是正号的，换句话说，就是忽略符号的影响，而实际减法实现中，是带符号的。如果还是直接做减法，就要分析四种情况下，A和B的比较情况，代码可读性差，而把减法的负号放进B里边，变成加法的计算显然更加清晰易懂。
还记得我们写辅助函数时写过一个东西吗：
void subtract() {
if (compare()) result = subtract(A, B);
else result = subtract(B, A);
}
vector<int> subtract(vector<int> A, vector<int> B) {
}你看，你以为调用时，加法和减法的关系是这样的：
实际上，它们的关系是这样的：
这个subtract(A, B)是一个辅助函数，前边我们只点出来了，却没有实现，因为它实现的逻辑实际上是减法，所以放到这里来写。
subtrac(A, B)的实现
vector<int> subtract(vector<int> preArr, vector<int> nextArr) {
vector<int> alignedPre = align(preArr);
vector<int> alignedNext = align(nextArr);
vector<int> res(BIT_NUM, 0);
for (int i=BIT_NUM-1; i>=0; i--) {
res[i] += alignedPre[i] - alignedNext[i];
if (res[i] < 0) {
res[i-1] -= 1;
res[i] += 10;
}
}
//整理
vector<int> _res;
int i = 0;
while (res[i] == 0) {
i++;
}
int j = i;
while (j != BIT_NUM) {
_res.push_back(res[j]);
j++;
}
if (_res.empty()) {
_res.push_back(0);
}
return _res;
}如果你理解了前边加法的实现，这段代码是非常好理解的，逻辑都差不多，唯一需要注意的就是，绝对值的计算，在加法中，计算结果是不可能出现0的，而减法会出现0的情况，这时候，_res.push_back()是不被执行的，_res是为空的，而我们的计算结果应该是0，所以我们要给它放个0进去。
5. 乘法实现
1. 确定符号
符号的确定很简单，同号为正，异号为负。
2. 将AB反转
vector<int> reversedPre = reverse(preArr);
vector<int> reversedNext = reverse(nextArr);3. 代入公式 res[i+j] = A[i] * B[j]
resArr.clear();
resArr.resize(BIT_NUM, 0);
for (int i=0; reversedPre[i] != -1; i++) {
for (int j=0; reversedNext[j] != -1; j++) {
resArr[i+j] += reversedPre[i] * reversedNext[j];
if (resArr[i+j] > 9) {
resArr[i+j+1] += resArr[i+j] / 10;
resArr[i+j] %= 10;
}
}
}4. 整理
vector<int> _res;
int i;
for (i=BIT_NUM-1; i>=0; i--) {
if (resArr[i] != 0) {
break;
}
}
while (i >= 0) {
_res.push_back(resArr[i]);
i--;
}
resArr = _res;我们计算一下123*45 = 5535，通过以上方法我们得到这样一个结果：
先让i走到正确的位置：
然后让i往左走，遇到的值都插入到_res的尾部中，这样_res的值就是5535，就是我们要的答案了
6. 除法实现
首先B不能为0，否则直接返回。
1. 确定符号
同号为正，异号为负。
2. 除法计算
当A < B时，结果为0
当A > B时
我们来分析一下，首先会让8和33做比较，发现8<33，比较结果是小于，于是我们会让85和33做比较，发现85>33 ，比较结果是大于，当然，还有比较结果是等于的情况。
我们发现，需要另起一个数组，来保存8，85这些要跟B比较的值，我们把它命名为tmp。
我们来看一下这3种情况：
比较结果是小于时，我们会让指针p往右走一位， 然后把A[p]加到tmp的尾部
if (compare(tmp) == -1){
//若tmp<B
p++;
tmp.push_back(preArr[p]);
}比较结果是大于时，我们先让85-33=52，接着判断52和33的关系，也是大于，接着减52-33 = 19，发现19小于33，就可退出循环了，这时我们做了2次减法，就可以得到一个2。
if (compare(tmp) == 1) {
//若tmp>B
//若前大后小 则一直减 至前小于或等于后
while (compare(tmp) == 1) {
for (int i=tmp.size(); i<BIT_NUM; i++) {
tmp.push_back(-1);
}
tmp = subtract(tmp, nextArr);
resArr[p]++;
}
} 上面代码有一个for循环是给tmp尾部添-1的，因为我们做减法的时候，subtract(A，B)是有格式要求的，前边是数据，接着的是-1做标记，长度也是有要求的，为BIT_NUM。
比较结果是等于时，tmp要清空，而不是为0，如果为0，A[p]加过来的时候，就会出现03这样的情况，有前导0，不是我们想要的，如果清空的话，加过来后tmp是3，就是我们想要的。
if (compare(tmp) == 0){
//若tmp=B
resArr[p] += 1;
tmp.clear();
}这里其实还有一种情况，就是tmp清空后，compare(tmp)会返回2，我们需要找一个不为0的A[p]加到tmp尾部即可。
if (compare(tmp) == 2){
//若tmp为空
p++;
while (preArr[p] == 0 && p != preArrSize) {
p++;
}
if (p != preArrSize) {
tmp.push_back(preArr[p]);
}
}完整代码：
if (compareRes) {
int p = 0;
//tmp用来保存当前被B除的数
vector<int> tmp;
tmp.push_back(preArr[p]);
while (p != preArrSize) {
if (compare(tmp) == 1) {
//若tmp>B
//若前大后小 则一直减 至前小于或等于后
while (compare(tmp) == 1) {
for (int i=tmp.size(); i<BIT_NUM; i++) {
tmp.push_back(-1);
}
tmp = subtract(tmp, nextArr);
resArr[p]++;
}
} else if (compare(tmp) == -1){
//若tmp<B
p++;
tmp.push_back(preArr[p]);
} else if (compare(tmp) == 0){
//若tmp=B
resArr[p] += 1;
tmp.clear();
} else {
//若tmp为空
p++;
while (preArr[p] == 0 && p != preArrSize) {
p++;
}
if (p != preArrSize) {
tmp.push_back(preArr[p]);
}
}
}
resArr[p] = -1;
}和上边分析的差不多，唯一区别的点就是最后我们给计算结果尾部放个-1做标记。
3. 整理
vector<int> _res;
int i = 0;
while (resArr[i] == 0) {
i++;
}
if (i == BIT_NUM) {
_res.push_back(0);
resArr = _res;
return;
}
int j = i;
while (resArr[j] != -1) {
_res.push_back(resArr[j]);
j++;
}
resArr = _res;整理的逻辑已经写过很多次了，应该不难理解。
7. 取余实现
利用公式 A%B = A - (A/B) * B，而减法、除法、乘法我们都实现了，直接调用即可
要注意的是，我们做取余操作时，为了方便，会先把AB都变为正号，计算结果的符号另做讨论。
接下来直接看代码吧：
void mod() {
if (nextArr[0] == 0) {
cout << "分母不能为0" << endl;
return;
}
// 先将A和B的值保存起来
vector<int> preTmp = preArr;
char preSingTmp = preSing;
vector<int> nextTmp = nextArr;
char nextSintTmp = nextSing;
// AB都变为正号
preSing = '+';
nextSing = '+';
// 先完成除法
divide();
// 让除法算出后的结果当A并格式化处理，B还是原来的B 做乘法
preArr = resArr;
for (int i=preArr.size(); i<BIT_NUM; i++) {
preArr.push_back(-1);
}
multiply();
// 让原先的A做A，乘法计算出来的结果做B并格式化处理 做减法
preArr = preTmp;
nextArr = resArr;
for (int i=nextArr.size(); i<BIT_NUM; i++) {
nextArr.push_back(-1);
}
subtract();
// 把原先的值都还原回来
nextArr = nextTmp;
nextSing = nextSintTmp;
preSing = preSingTmp;
// 确认符号
if (preSing == '-' && nextSing == '-') {
resSing = '-';
} else if (preSing == '-' && nextSing == '+') {
resSing = '-';
} else {
resSing = '+';
}
}总结
至此，我们实现了BigInt的加减乘除以及取余操作，在实现这些操作之前，我们对其进行分析，写了一些必要的辅助函数使实现过程事半功倍。在写减法时，为了使代码可读性增加，我们把减法转为加法；在写这些加减乘除的操作时，其实不难发现，它们的步骤是差不多的，都是确认符号，计算结果，整理结果。在写这些方法前，我们先写了打印函数，这样会给debug时提供方便。
最后
以上就是雪白牛排为你收集整理的BigInt加减乘除操作实现详解前言一、抽象数据类型BigInt二、辅助方法 三、高精度加减乘除类 四、加减乘除的实现总结的全部内容，希望文章能够帮你解决BigInt加减乘除操作实现详解前言一、抽象数据类型BigInt二、辅助方法 三、高精度加减乘除类 四、加减乘除的实现总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复