[原创][c++]高精度运算算法（一）：加法与减法

创造发现
1

背景

  我们知道，c++可表示的整型数据最大值是2^64-1。然而，当需要计算一个非常大的整数时，如果使用计算机内部的整型数据类型，就可能会导致数据溢出或精度不足的问题。此时，我们需要高精度算法。
  高精度算法通过使用字符串或数组等方式来表示数字，从而可以避免这些问题，并且能够进行更高精度的计算。

教学

 我们需要写出四个部分的代码：输入、存储、运算和输出。

1. 输入

由于要输入的数字可能很大，因此我们用string类型来输入。

string charA;
int a[];
getline(cin, charA);

2. 存储

我们需要将字符串中的数字存储到数组中，这样才能在接下来的步骤中参与运算。

void init(string s, int a[])//initialization
{
    int len = s.length();
    for (int i = 0; i < len; i++)
    {
        a[i] = s[len - i - 1] - '0';//'x' - '0' = x - 0
    }
}

众所周知，字符串可以看作一个字符数组，因此我们可以将里面的数取出来，利用字符所对应的ASCII码把字符转换成数字，并逆序存储在数组a中。

  • 逆序存储的原因是让下标数字大小与位次的高低相对应，例如12345存入数组中是{5,4,3,2,1}，便于计算。

3. 运算和输出

3.1 加法

void add(string &charA, string &charB)
{
    int a[256] = {0}, b[256] = {0};
    init(chara, a);
    init(charb, b);
    int lenA = charA.length(), lenB = charB.length();//获取数组a和b的长度
    
    int maxlen = max(lenA, lenB);//取长度的最大值
    int sum[256] = {0};//a与b的和。记得初始化！
    
    for (int i = 0; i < maxlen; i++)//每一位相加后存储到sum的相应位置
    {
        sum[i] = a[i] + b[i];
    }
    for (int i = 0; i < maxlen; i++)//处理进位。>10时就要进1
    {
        sum[i+1] += sum[i] / 10;
        sum[i] %= 10;
    }


    if(sum[maxlen] > 0)//当最高位进位值不为0时，增加位数
    {
		maxlen++;
	} 
    
    for (int j = maxlen - 1; j >= 0; j--)//逆序输出数组内容
    {
        cout << sum[j];
    }
    cout << endl;
}

它的核心算法，还有另一种写法。

sum[i] = a[i] + b[i];//相加
if (a[i] < b[i])//进位
{
    sum[i] %= 10;
    sum[i+1]++;
}

3.2 减法

void subtract(string& charA, string& charB)
{
    int a[256] = {0}, b[256] = {0};
    init(charA,a);
    init(charB,b);
    int lenA = charA.length(), lenB = charB.length()
    
    string n; //中间变量
    int c[256] = {0}, lenC;//存储结果的数组及其长度

    //判断减数是否比被减数大（仅限正数）
    if (lenA < lenB || (lenA == lenB && charA.compare(charB) < 0))//compare()是c++风格的，strcmp是c风格的
    {
        n = charB;
        charB = charA;
        charA = n;
        cout << "-";//输出负号
    }
    init(charA, a);
    init(charB, b);

    int i = 0;
    for (i; i < lenA || i < lenB; i++)
    {
        if (a[i] < b[i])
        {
            a[i] += 10;//向高位借10
            a[i+1] -= 1;
        }
        c[i] = a[i] - b[i];
    }
    lenC = i;
    while (c[lenC - 1] == 0 && lenC > 1) lenC--;//删去最高位的0

    for (int j = lenC - 1; j >= 0; j--)//逆序输出
    {
        cout << c[j];
    }
    cout << endl;
}

(注：以上代码不支持输入负数。如有需求可以挑战一下。)

1 个赞
2

写得不错噢～～～

2 个赞