经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
高精度加法(C语言实现)
来源:cnblogs  作者:凉茶coltea  时间:2023/11/6 9:12:10  对本文有异议

高精度加法(C语言实现)

介绍

众所周知,整数在C和C++中以intlonglong long三种不同大小的数据存储,数据大小最大可达2^64,但是在实际使用中,我们仍不可避免的会遇到爆long long的超大数运算,这个时候,就需要我们使用高精度算法,来实现巨大数的运算。

高精度的本质是将数字以字符串的形式读入,然后将每一位分别存放入int数组中,通过模拟每一位的运算过程,来实现最终的运算效果。

今天,我们先讲解高精度加法的C语言实现:


声明

但其实我这版C语言的高精度算法封装是很有问题的,没有stl,字符串的操作是比较繁琐的,以后熟悉C++后我会再写一版简易的,标准的高精度算法解析,但通过本文了解高精度的思路也是没有问题的。


代码实现

  1. #include<stdio.h>
  2. const int N = 100001;
  3. int add(int a[], int b[], int c[], int len1, int len2)
  4. {
  5. int t = 0, i = 0, max = len1 > len2 ? len1 : len2;
  6. //max指两加数中较大者的位数,两数之和c位数至少是max
  7. //标识变量t值为0或1,代表是否进位,初始为0
  8. for (; i <= max; i++)//运算到较大者位数后一位停止
  9. {
  10. c[i] = (a[i] + b[i] +t) % 10;//c的每一位为两数该位之和加上t再模去10
  11. t = (a[i] + b[i] + t) / 10;//若和>10,则c[i]取其个位,t取其十位
  12. }//i遍历至max+1
  13. if (c[i - 1] == 1) return i;//若最高位为1,则返回c长度为max+1,即i
  14. else return i - 1;//否则返回max,即i-1
  15. }
  16. int main()
  17. {
  18. char str1[N], str2[N];//两个数的字符串形式
  19. int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };//ab为加数,c为和
  20. char x;
  21. int len1 = 0, len2 = 0;//两数位数
  22. do {
  23. scanf("%c", &x);
  24. str1[len1++] = x;
  25. }while (x != '\n');
  26. do{
  27. scanf("%c", &x);
  28. str2[len2++] = x;
  29. } while (x != '\n');
  30. len1--; len2--;//将数据读入str1和str2,同时记录位数
  31. for (int i = len1 - 1; i >= 0; i--)
  32. a[i] = str1[len1 - i - 1]-'0';
  33. for (int i = len2 - 1; i >= 0; i--)
  34. b[i] = str2[len2 - i - 1] - '0';//将ab的每一位转换为整形存入数组
  35. int len3 = add(a, b, c, len1, len2);//执行高精度加法函数
  36. for (int i = len3 - 1; i >= 0; i--)
  37. printf("%d", c[i]);//输出
  38. return 0;
  39. }

思路分析

对大数来说,输入便已经是一个有些麻烦的问题,无法读取整形,只能以字符串形式,而且连有几位数字都不知道。

  1. char str1[N], str2[N];//两个数的字符串形式
  2. int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };//ab为加数,c为和
  3. char x;
  4. int len1 = 0, len2 = 0;//两数位数
  5. do {
  6. scanf("%c", &x);
  7. str1[len1++] = x;
  8. }while (x != '\n');
  9. do{
  10. scanf("%c", &x);
  11. str2[len2++] = x;
  12. } while (x != '\n');
  13. len1--; len2--;//将数据读入str1和str2,同时记录位数

这里是主函数的变量声明和输入部分,若是程序只运行一次高精度运算,我们可以把变量的声明放在主函数以外,来能减少函数的参数个数。

我们将读取的字符赋值给x,然后再放入字符串数组,最后对x进行判断,若x为换行符、空格或其他标识着数据输入结束的字符,则终止循环。

同时,循环中变化的数组下标我们直接记为len1len2,代表两个数字的长度。


显然,字符形式的数字并不好运算,所以,我们需要将每一位转换为整形存入数组,方便后续的计算。

那此时我们就会遇到一个问题,数组的第0位应该存放最高位还是存放个位呢?先看代码实现:

  1. for (int i = len1 - 1; i >= 0; i--)
  2. a[i] = str1[len1 - i - 1]-'0';
  3. for (int i = len2 - 1; i >= 0; i--)
  4. b[i] = str2[len2 - i - 1] - '0';//将ab的每一位转换为整形存入数组

在这段函数中,我们从高位向低位,将每一位的字符-'0',得到他的整形,然后存入数组,最终得到从低位到高位的新数组。

为什么要反过来存放呢,这就要考虑到一个最高位进位的问题。

数组后面存放最高位,在最高位进位时显然比最高位放在第0位操作起来更方便,前者只需要在下一位+1,而后者想要进位,可能只能依靠于额外的标记变量了。

这种问题在后面的高精度乘法中更是明显,所以,在高精度运算中,为了使高位灵活变动,我们一般都采用倒序的存放顺序,即数组前面存低位,后面存高位。


到这里,我们就将准备工作做完了,数字已经放入数组,长度也已得知,这时我们就需要写一个函数来运行高精度加法,代码如下:

  1. int add(int a[], int b[], int c[], int len1, int len2)
  2. {
  3. int t = 0, i = 0, max = len1 > len2 ? len1 : len2;
  4. //max指两加数中较大者的位数,两数之和c位数至少是max
  5. //标识变量t值为0或1,代表是否进位,初始为0
  6. for (; i <= max; i++)//运算到较大者位数后一位停止
  7. {
  8. c[i] = (a[i] + b[i] +t) % 10;//c的每一位为两数该位之和加上t再模去10
  9. t = (a[i] + b[i] + t) / 10;//若和>10,则c[i]取其个位,t取其十位
  10. }//i遍历至max+1
  11. if (c[i - 1] == 1) return i;//若最高位为1,则返回c长度为max+1,即i
  12. else return i - 1;//否则返回max,即i-1
  13. }

虽然图中解析已经非常到位了,但我还是简单讲解一下吧。

首先从i=0位开始,将a[i]b[i]t相加,其个位便是c在该位的值,所以我们对他模上10,其大于10时需要进位,那我们就将其除以10,整形除法下取整,得到10,作为t的值,来参与下一位的运算。

最后,我们通过对最高位的01判断,来决定返回max还是max+1


这时,我们已经将结果存入c了,只差输出了,但想要输出我们怎么知道c有几位呢?最高位到底有没有进位呢?那其实我们的函数返回值就是c的长度了。

  1. int len3 = add(a, b, c, len1, len2);//执行高精度加法函数
  2. for (int i = len3 - 1; i >= 0; i--)
  3. printf("%d", c[i]);//输出

这样,我们从后往前一位位输出,就得出了最终结果了。


总结

总而言之言而总之,高精度算法就是单独将每一位数字存入数组,分别计算,模拟我们手动计算的过程,接下来的减法和乘法除法的核心思想都是这个,那么以上便是对高精度加法算法的介绍,本文由凉茶coltea撰写,思路来自AcWing,大佬yxc的课程。

原文链接:https://www.cnblogs.com/coltea/p/17809261.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号