高精度计算
有些数值计算要求精度高，希望计算的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度，利用计算机处理高精度计算应注意以下问题：
<1>数据的接收与存贮
①利用字符串读入数据
a[i]=s[s.length()-i]-'0';
②直接用循环加数组方法输入数据
注意：倒序存储
<2>确定位数
位数即为字符串长度
<3>进位，借位处理
①加法进位
c[i]=a[i]+b[i];
if(c[i]>=10){c[i]%=10;c[i+1]++;}
②减法借位
if(a[i]<b[i]){a[i+1]--;a[i]+=10;}
c[i]=a[i]-b[i];
③乘法进位
c[i+j-1]=a[i]*b[i]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;
<4>商和余数的求法：视被除数和除数的位数情况进行处理


下附高精度加法C++程序

#include<cstdio>
#include<cstring>
using namespace std;

int main()
{
	char a1[100],b1[100];
	int a[100],b[100],c[100],lena,lenb,lenc,i,x;

	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
        printf("加数1：");
	gets(a1);
	printf("加数2：");
	gets(b1);
        lena=strlen(a1);
	lenb=strlen(b1);
	for (i=0;i<=lena-1;i++)     a[lena-i]=a1[i]-48;
	for (i=0;i<=lenb-1;i++)     b[lenb-i]=b1[i]-48;
	lenc=1;
	x=0;
	while(lenc<=lena||lenc<=lenb)
	{
		c[lenc]=a[lenc]+b[lenc]+x;
		x=c[lenc]/10;
		c[lenc]%=10;
		lenc++;
	}
	c[lenc]=x;
	if (c[lenc]==0)     lenc--;
        printf("和：   ");
	for (i=lenc;i>=1;i--)
        {
        	printf("%d",c[i]);
        }
	printf("\n");
	return 0;
}

 
;计算X+Y=Z
;X=001565A0H，Y=0021B79EH，运算的结果Z=00371D3EH。
DATA SEGMENT
MES DB  'The result is:$'
XL  DW 65A0H
XH  DW 0015H
YL  DW 0B79EH
YH  DW 0021H
DATA ENDS
 
CODE SEGMENT
   ASSUME CS:CODE,DS:DATA
START: MOV AX,DATA
  MOV DS,AX
  MOV  DX,OFFSET MES  ;显示信息
  MOV  AH,09H
  INT   21H
  MOV   AX,XL   
  ADD   AX,YL  ;Y低位数值与X低位数值相加  
  MOV   BX,AX   ;BX中存放结果的低16位
  MOV   AX,XH
  ADC   AX,YH   ;Y高位数值与X高位数值相加
  MOV  CX,AX    ;CX中存放结果的高16位
   ;显示结果
    MOV DH,CH
    CALL SHOW
    MOV DH,CL
    CALL SHOW
    MOV DH,BH
    CALL SHOW
    MOV DH,BL
    CALL SHOW 
    MOV AX,4C00H
    INT  21H 
SHOW PROC NEAR
      PUSH DX
      PUSH AX
       MOV	AL,DH
	   AND	AL,0F0H			
	   ;取高4位
	   SHR	AL,4
	   CMP	AL,0AH			;是否是A以上的数
	   JB	C2		
	   ADD	AL,07H		
C2:	   ADD	AL,30H	
	
	   MOV	DL,AL			;show character 
	   MOV	AH,02H
	   INT	21H
 
	   MOV	AL,DH
	   AND	AL,0FH			;取低4位
	   CMP	AL,0AH
	   JB	C3
	   ADD 	AL,07H
C3:	   ADD	AL,30H
	   MOV	DL,AL			;show character 
	   MOV	AH,02H
	   INT	21H
	   POP AX
	   POP DX
	   RET
SHOW   ENDP
CODE ENDS
       END   START
 

C++中数据存储的范围是有限的，最长的longlong型最大只能存储2^63-1。如果要是需要存储更大的数就只能使用数组了。这样存储的数的运算需要另外编写程序。

这里介绍高精度加法

这种加法的运算类似于小学学习的竖式，从个位开始，逐位相加，如果大于10，则需进1。

首先我们需要先读入数据，这里使用一个字符串读入，由于读入时首位是最大位，而运算时需要从个位开始，再将字符串反序的存储到一个整形数组之中，字符串的存储采用的是ASCII码，转换时，需要减去’0’。然后逐位相加即可，定义一个辅助变量记录进位。最后还需反序输出。

点击查看 高精度数的四则运算
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1e5;
char s1[N],s2[N];
int a[N],b[N],ans[N];

int main()
{
	cin>>s1>>s2;
	int len1=strlen(s1);
	for(int i=1;i<=len1;i++)
		a[i]=s1[len1-i]-'0';				//反序存储 
	int len2=strlen(s2);
	for(int i=1;i<=len2;i++)				
		b[i]=s2[len2-i]-'0';
	int len=max(len1,len2);					//长度最长的加1为答案长度 
	int tmp=0;								//存进位 
	for(int i=1;i<=len+1;i++)
	{
		ans[i]=a[i]+b[i]+tmp;
		tmp=ans[i]/10;						//除10，进位 
		ans[i]=ans[i]%10;					//模10，本位 
	}
	if(ans[len+1]!=0)
		cout<<ans[len+1];					//len+1位可能没有 
	for(int i=len;i>=1;i--)
		cout<<ans[i];						//反序输出 
	return 0;
}

C++: 高精度加法与高精度减法

标签：C++  高精度加法 高精度减法

by 小威威

在学C语言的时候，我有实现过高精度乘法(想了解的戳它)。 

其实高精度加法、减法比乘法简单多了，所以可以通过高精度乘法这篇文章来入门高精度的算法。

现在是用C++实现，显然有了string类，一切的操作都变的简单多了。

题目如下：(Author: 欧文杰(TA)) 

This is an easy big integer. Your task is to finish the class big integer:

Tips:

size_ means the size of  the big integer

friend function should have been declared outside;

when you declare the friend function, you should forward declare the class.

when you cannot compile, try to read the informations or google it.

overload “<<” : please output like this format: “123456”, no wrap.

overload “-“: we promise that a >= b when a - b .

其中，main.cpp 与 BigInteger.h已给出。



\\ main.cpp
#include "BigInteger.h"
#include <iostream>
#include <string>
using namespace std;

int main() {
  string s1, s2, s3, s4;
  cin >> s1 >> s2;
  cin >> s4;
  BigInteger a(s1);
  BigInteger b(s2);
  BigInteger c(a);
  BigInteger d(s4);
  BigInteger sum(a+b);
  BigInteger diff(c-d);
  cout << sum << endl;
  cout << diff << endl;
  return 0;
}

\\ BigInteger.h
#ifndef _BIG_INTEGER_
#define _BIG_INTEGER_

#include <iostream>
#include <string>
using std::string;
using std::ostream;

// forward declaration
class BigInteger;

// operators overloading
BigInteger operator+(const BigInteger& left, const BigInteger& right);
BigInteger operator-(const BigInteger& left, const BigInteger& right);
ostream& operator<<(ostream& out, const BigInteger& Bint);

class BigInteger {
 public:
  BigInteger();
  explicit BigInteger(const string& number);
  BigInteger(const BigInteger& other);
  friend BigInteger operator+(const BigInteger& left,
                              const BigInteger& right);

  // promise left >= right
  friend BigInteger operator-(const BigInteger& left,
                              const BigInteger& right);
  friend ostream& operator<<(ostream& out, const BigInteger& Bint);
  ~BigInteger();

 private:
  int *data_;
  int size_;
};

#endif  // _BIG_INTEGER_

现在我主要来讲解一下如何实现高精度加法与减法。 

先交代一下背景，我们用string对象接受a,b，然后再将它们存储到数组中进行高精度的操作。



1.高精度加法(a+b)

实现高精度加法，我们可以先将整个数组看成一个很大的数字，其中数组的每个元素相当于这个数字的一个位。那么实现这两个很大的数字的加法可以采用“先对应位相加，后进行进位操作”的策略。

先来谈谈对应位相加。要实现对应位相加，也就是实现下标相同的数组元素的相加。这时要注意了，两个数字的位数不同，故数组的元素数目也不同，如果只是简单的用for循环实现数组对应位相加的话，会产生错误，因为数组可能会出现越界引发不可预估的错误。这种情况下，说明要先判断两个数据的位数大小，然后取max_size(a,b)+1作为存储结果的数组大小(加1的原因是加法可能会产生进位，从而使数据的位数增多)。所以在相加之前，我们要先判断大小。接着，又有一个问题。数字相加是对应位相加，如果我们数组按照高位到低位的形式存储数据，那么会导致对应位的相加不那么方便，因为对应位的数组元素的坐标不同。因此我们可以选择将数据倒着存储，这样就可以用相同下标的数组元素相加来实现对应位的相加。

再谈谈进位操作。进位操作最好是在对应位相加完之后再进行，因为我们采用的相加顺序是从低位到高位，倘若你在对应位相加后进行进位操作，那么下一个对应位相加便会覆盖结果中对应位的数据导致进位丢失。进位操作很简单，就是一个取余与除法的问题，这里就不再强调了。

对于结果中最高的那一位，有可能存在也有可能不存在，这都是取决于倒数第二位。可以有这样的思路，如果倒数第二位需要进位，我们就将数组允许访问的大小加1(通常我们都是设置一个比较大的数组，然后再用一个成员size来限制数组被访问的区域)；如果倒数第二位不需要进位，我们可以对size不进行任何操作。这个思路是标程的做法，所以不会在我待会的代码里出现，在这里仅是扩展一下思路而已。



2.高精度减法(a-b)

由于题目的限制，a是>=b的(如果没有这个前提，那就要像上面的加法一样进行判断大小)。实现减法与实现加法的原理差不多，现在主要说明一下与高精度加法的不同点。

对于加法来说，是max_size(a, b)+1，而对于减法是max_size(a, b)。因为不会出现进位操作。然而，虽然没有进位，但是有退位呀，所以会出现结果数组的高位出现无意义0的情况，如000001200(指1200),在这里有两种处理方法：第一种就是修改数组被访问区域的大小，也就是size–，另一种方法就是在输出中进行筛选，自动过滤掉无意义的0。

下面我将呈现个人的代码：



# include "BigInteger.h"

BigInteger :: BigInteger() {
    data_ = NULL;
    size_ = 0;
}

BigInteger :: BigInteger(const string& number) {
    data_ = NULL;
    size_ = 0;
    data_ = new int[number.size()];
    int j = 0;
    for (int i = number.size()-1; i >= 0; i--) {
        data_[j] = number[i] - '0';
        j++;
    }
    size_ = number.size();
}

BigInteger :: BigInteger(const BigInteger& other) {
    data_ = NULL;
    size_ = other.size_;
    data_ = new int[size_];
    for (int i = 0; i < size_; i++) {
        data_[i] = other.data_[i];
    }
}

BigInteger operator+(const BigInteger& left,
                              const BigInteger& right) {
    BigInteger copy;
    if (left.size_ < right.size_) {
        copy.size_ = right.size_+1;
        copy.data_ = new int[copy.size_];
        copy.data_[copy.size_-1] = 0;
        for (int i = 0; i < right.size_; i++) {
            if (i < left.size_) {
                copy.data_[i] = left.data_[i] + right.data_[i];
            } else {
                copy.data_[i] = right.data_[i];
            }
        }
        for (int i = 0; i < right.size_; i++) {
            if (copy.data_[i] >= 10) {
                copy.data_[i+1]++;
                copy.data_[i] -= 10;
            }
        }
    } else {
        copy.size_ = left.size_+1;
        copy.data_ = new int[copy.size_];
        copy.data_[copy.size_-1] = 0;
        for (int i = 0; i < left.size_; i++) {
            if (i < right.size_) {
                copy.data_[i] = left.data_[i] + right.data_[i];
            } else {
                copy.data_[i] = left.data_[i];
            }
        }
        for (int i = 0; i < left.size_; i++) {
            if (copy.data_[i] >= 10) {
                copy.data_[i+1]++;
                copy.data_[i] -= 10;
            }
        }
    }
    return copy;
}

// promise left >= right
BigInteger operator-(const BigInteger& left,
                              const BigInteger& right) {
    BigInteger copy;
    copy.size_ = left.size_;
    copy.data_ = new int[left.size_];
    for (int i = 0; i < left.size_; i++) {
        if (i < right.size_) {
            copy.data_[i] = left.data_[i] - right.data_[i];
        } else {
            copy.data_[i] = left.data_[i];
        }
    }
    for (int i = 0; i < left.size_; i++) {
        if (copy.data_[i] < 0) {
            copy.data_[i+1]--;
            copy.data_[i] += 10;
        }
    }
    return copy;
}

ostream& operator<<(ostream& out, const BigInteger& Bint) {
    int key = 0;
    for (int i = Bint.size_-1; i >= 0; i--) {
        if (Bint.data_[i] != 0) key = 1;
        if (Bint.data_[i] == 0 && key == 0) continue;
        out << Bint.data_[i];
    }
    int j;
    for (j = 0; j < Bint.size_; j++) {
        if (Bint.data_[j] != 0) break;
    }
    if (j == Bint.size_) {
        out << 0;
    }
    return out;
}

BigInteger :: ~BigInteger() {
    if (data_ != NULL)
        delete[] data_;
}




3.内存错误

在这道题有个地方很容易出现内存错误，这个错误我debug了不久才找出来的。就是用new分配一段内存，这段内存在没有初始化的条件下除了执行初始化操作以外的所有操作都是非法访问。这一点要非常注意。

如程序里的实现高精度加法那里：



copy.data_[copy.size_-1] = 0;

这个是对最高位的初始化，如果没有初始化，不能执行++操作，这种操作是非法的。

以上内容皆为本人观点，欢迎大家提出批评和指导，我们一起探讨！