当前位置： 首页 > news >正文

C/C++高精度算法的实现

news 2026/5/31 6:58:13

做ACM题的时候，经常遇到大数的加减乘除，乘幂，阶乘的计算，这时给定的数据类型往往不够表示最后结果，这时就需要用到高精度算法。高精度算法的本质是把大数拆成若干固定长度的块，然后对每一块进行相应的运算。这里以考虑4位数字为一块为例，且输入的大数均为正整数（也可以考虑其他位，但要注意在每一块进行相应运算时不能超出数据类型的数值范围；有负整数的话读入时判断一下正负号在决定运算）。

1. 高精度加法

以3479957928375817 + 897259321544245为例：

3479957928375817
+897+2593+2154+4245
====
437612172499110062
进位0进位1进位0进位1
4377217249920062

C语言实现代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 200

//整数乘幂运算函数

intPow(inta,intb)

{

inti = 0, result = 1;

for(i = 0; i < b; ++i)

{

result *= a;

}

returnresult;

}

//High Precision Of Addition

intmain()

{

charstra[N], strb[N];//字符串数组，以字符形式储存两个大数；

inti = 0, step = 4, carry = 0;//step表示块长，carry为进位位；

intlengtha, lengthb, maxlength, resultsize;//maxlength表示stra和strb二者长度较大的那个；

intnuma[N], numb[N],numc[N];//依次储存被加数，加数，和；

memset(numa, 0,sizeof(numa));

memset(numb, 0,sizeof(numb));

memset(numc, 0,sizeof(numc));//初始化为零；

scanf("%s%s", stra, strb);

lengtha =strlen(stra);

lengthb =strlen(strb);//计算两个大数的长度

//字符数字转为四位一块的整数数字

for(i = lengtha-1; i >= 0; --i)

{

numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);

}

for(i = lengthb-1; i >= 0; --i)

{

numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);

}

maxlength = lengtha > lengthb ? lengtha : lengthb;

//逐块相加，并进位

for(i = 0; i <= maxlength/step; ++i)

{

numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry;//计算和

carry = (numa[i] + numb[i])/Pow(10, step);//计算进位

}

//计算最后和的块的总数

resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;

printf("%d", numc[resultsize]);

for(i = resultsize-1; i >= 0; --i)

{

printf("%04d", numc[i]);//右对齐，补零输出；

}

printf("\n");

return0;

}

2. 高精度减法

与加法类似，不同的是要注意正负号和显示位数的变化。以99999037289799 - 100004642015000为例：

先判断被减数和减数哪个大，显然这里减数大，故输出结果为负数。在用大数减去小数，（若某一块相减为负数，则要向高位块借位）如下表

100004642015000
-99-9990-3728-9799
1564735201
借位0借位1借位0借位1
0564725201

C语言实现代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 200

//整数乘幂运算函数

intPow(inta,intb)

{

inti = 0, result = 1;

for(i = 0; i < b; ++i)

{

result *= a;

}

returnresult;

}

//High Precision Of Subtraction

intmain()

{

charstra[N], strb[N];//字符串数组，以字符形式储存两个大数；

inti = 0, step = 4, borrow = 0, mark = 0;//step表示块长，borrow为借位位, mark为结果符号位；

intlengtha, lengthb, maxlength, resultsize;//maxlength表示stra和strb二者长度较大的那个；

intnuma[N], numb[N],numc[N], *maxnum, *minnum;//依次储存被减数，减数，和；

memset(stra, 0,sizeof(stra));

memset(strb, 0,sizeof(strb));

memset(numa, 0,sizeof(numa));

memset(numb, 0,sizeof(numb));

memset(numc, 0,sizeof(numc));//初始化为零；

scanf("%s%s", stra, strb);

lengtha =strlen(stra);

lengthb =strlen(strb);//计算两个大数的长度

maxlength = lengtha >= lengthb ? lengtha : lengthb;

//字符数字转为四位一块的整数数字

for(i = lengtha-1; i >= 0; --i)

{

numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);

}

for(i = lengthb-1; i >= 0; --i)

{

numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);

}

//找出较大的数

maxnum = numa;

minnum = numb;

mark = 1;

for(i = (maxlength-1)/step; i >= 0; --i)

{

if(numa[i] > numb[i])

{

maxnum = numa;

minnum = numb;

mark = 1;

break;

}

elseif(numa[i] < numb[i])

{

maxnum = numb;

minnum = numa;

mark = -1;

break;

}

}

//逐块相减，并借位

for(i = 0; i <= maxlength/step; ++i)

{

numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step);//计算差

borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1;//计算借位

}

//计算最后和的块的总数

resultsize = maxlength/step;

while(!numc[resultsize]) --resultsize;

printf("%d", mark*numc[resultsize]);

for(i = resultsize-1; i >= 0; --i)

{

printf("%04d", numc[i]);//右对齐，补零输出；

}

printf("\n");

return0;

}

3. 高精度乘法

乘法可以看作是乘数每一位与被乘数相乘后再相加，以4296556241 x 56241为例：

被乘数4296556241
乘数56241
被乘数x乘数4296556241
14296556241
4168*1038620*1024964*10
284*10019310*10012482*100
6252*100057930*100037446*1000
5210*1000048275*1000031205*10000
累加和2362122543006855351000081
进位（从低位向高位）2415430435100
积241642619550081

C语言实现代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 200

//整数乘幂运算函数

intPow(inta,intb)

{

inti = 0, result = 1;

for(i = 0; i < b; ++i)

{

result *= a;

}

returnresult;

}

//High Precision Of Multiplication

intmain()

{

charstra[N], strb[N];//字符串数组，以字符形式储存两个大数；

inti = 0, j = 0, k = 0, step = 4, carry = 0;//step表示块长，carry为进位位；

intlengtha, lengthb, resultsize, tmpsize, eachnum;//resultsize储存块的总数，eachnum用来储存乘数的每一位

intnuma[N], numb[N], numc[N], tmp[N];//依次储存被乘数数&积，乘数；

memset(numa, 0,sizeof(numa));

memset(numb, 0,sizeof(numb));

memset(numc, 0,sizeof(numc));//初始化为零；

scanf("%s%s", stra, strb);

lengtha =strlen(stra);

lengthb =strlen(strb);//计算两个大数的长度

//将被乘数字符数字转为四位一块的整数数字

for(i = lengtha-1; i >= 0; --i)

{

numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);

}

//将乘数数字字符数字转为一位一块的整数数字

for(i = lengthb-1; i >= 0; --i)

{

numb[lengthb-1-i] = strb[i]-'0';

}

resultsize = tmpsize = (lengtha-1)/step;

//取乘数的每一位与被乘数的逐块相乘，并进位；

for(i = 0; i < lengthb; ++i)

{

memcpy(tmp, numa,sizeof(numa));//将numa数组赋值给tmp数组；

k = i/step;//k储存每一块需要向高位块移动的次数；

if(k)

{

for(j = tmpsize; j >= 0; --j)

{

tmp[j+k] = tmp[j];

tmp[j] = 0;

}

tmpsize += k;

}

//乘以乘数每一位扩展成的块；

eachnum = numb[i]*Pow(10, i%step);

for(j = 0; j <= tmpsize; ++j)

{

tmp[j] *= eachnum;

}

//大数相加

carry = 0;//进位置零；

for(j = 0; j <= resultsize; ++j)

{

numc[j] += tmp[j] + carry;

carry = numc[j]/Pow(10,step);

numc[j] %= Pow(10, step);

}

if(carry)

{

++resultsize;

numc[j] += carry;

}

}

//输出

printf("%d", numc[resultsize]);

for(i = resultsize-1; i >= 0; --i)

{

printf("%04d", numc[i]);//右对齐，补零输出；

}

printf("\n");

return0;

}

4. 高精度除法

高精度除法有两种，一种是高精度除以低精度，另一种是高精度除以高精度。前者只需将每一块除以低精度除数即可；后者则考虑用高精度减法来实现，即每次减去高精度除数，直到减到小于除数，则减的次数即为商，剩余的即为余数。

高精度除以低精度
以9876342876 / 343为例：

被除数9876342876
除数343
向低位块进位98137190
商028794002
余数190

C语言代码实现如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 200

//整数乘幂运算函数

intPow(inta,intb)

{

inti = 0, result = 1;

for(i = 0; i < b; ++i)

{

result *= a;

}

returnresult;

}

//High Precision Of division

//(1)高精度除以低精度

intmain()

{

charstra[N];//字符串数组，以字符形式储存高精度被除数；

inti = 0, step = 4, carry = 0;//step表示块长，carry为高位向低位进位位；

intlengtha, resultsize;

intnuma[N], numb, numc[N], numd;//依次储存被除数，除数，商, 余数；

memset(numa, 0,sizeof(numa));

memset(numc, 0,sizeof(numc));//初始化为零；

scanf("%s%d", stra, &numb);

lengtha =strlen(stra);//计算被除数的长度

//字符数字转为四位一块的整数数字

for(i = lengtha-1; i >= 0; --i)

{

numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);

}

carry = 0;//高位向低位进位位置零

resultsize = (lengtha-1)/step;

//逐块相除，高位向低位进位

for(i = resultsize; i >= 0; --i)

{

numc[i] = (numa[i] + carry*Pow(10,step))/numb;//计算商

carry = (numa[i] + carry*Pow(10,step))%numb;//计算进位

}

numd = carry;//最低位块的余数即为整个除法的余数

//计算最后和的块的总数

while(!numc[resultsize]) --resultsize;

//输出商

printf("%d", numc[resultsize]);

for(i = resultsize-1; i >= 0; --i)

{

printf("%04d", numc[i]);//右对齐，补零输出；

}

//输出余数

printf("\n%d\n", numd);

return0;

}

高精度除以高精度
以176342876 / 3453452为例：

被除数176342876
- (51 x 除数)51 x 3453452
余数216824
商51

C语言代码实现如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 200

//整数乘幂运算函数

intPow(inta,intb)

{

inti = 0, result = 1;

for(i = 0; i < b; ++i)

{

result *= a;

}

returnresult;

}

//High Precision Of division

//(2)高精度除以高精度

intmain()

{

charstra[N], strb[N];//字符串数组，以字符形式储存两个大数；

inti = 0, step = 4, borrow = 0;//step表示块长，borrow为进位位；

intlengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark;//maxlength表示stra和strb二者长度较大的那个；

intnuma[N], numb[N], numc[N], numd[N];//依次储存被除数数，除数数，商，余数；

memset(stra, 0,sizeof(stra));

memset(strb, 0,sizeof(strb));

memset(numa, 0,sizeof(numa));

memset(numb, 0,sizeof(numb));

memset(numc, 0,sizeof(numc));

memset(numd, 0,sizeof(numd));//初始化为零；

scanf("%s%s", stra, strb);

lengtha =strlen(stra);

lengthb =strlen(strb);//计算两个大数的长度

//字符数字转为四位一块的整数数字

for(i = lengtha-1; i >= 0; --i)

{

numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);

}

for(i = lengthb-1; i >= 0; --i)

{

numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);

}

memcpy(numd, numa,sizeof(numa));

numbsize = (lengthb-1)/step;

numcsize = 0;

numdsize = (lengtha-1)/step;

do

{

maxsize = numdsize > numbsize ? numdsize : numbsize;

//计算剩余数是否小于除数

mark = 1;

for(i = maxsize; i >= 0; --i)

{

if(numd[i] > numb[i])

{

mark = 1;

break;

}

elseif(numd[i] < numb[i])

{

mark = -1;

break;

}

}

//判断是否余数已经小于除数

if(!(mark+1))break;

borrow = 0;//借位置零；

//逐块相减，并借位

for(i = 0; i <= maxsize; ++i)

{

tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step);//计算差

borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1;//计算借位

numd[i] = tmpnum;

}

while(!numd[numdsize]) --numdsize;

//每减一个除数，商加一；

borrow = 1;

for(i = 0; i <= numcsize; ++i)

{

numc[i] += borrow;

borrow = numc[i]/Pow(10,step);

numc[i] %= Pow(10,step);

}

if(borrow)

{

++numcsize;

numc[i] += borrow;

}

}while(1);

printf("%d", numc[numcsize]);

for(i = numcsize-1; i >= 0; --i)

{

printf("%04d", numc[i]);//右对齐，补零输出；

}

printf("\n");

printf("%d", numd[numdsize]);

for(i = numdsize-1; i >= 0; --i)

{

printf("%04d", numd[i]);//右对齐，补零输出；

}

printf("\n");

return0;

}

以上就是本文的全部内容，希望对大家的学习有所帮助


http://www.cnnetsun.cn/news/2526509.html

相关文章：

  • 告别仿真报错！手把手教你用Quartus II 18.1和ModelSim 10.5c创建第一个Testbench
  • 五分钟完成Node.js服务对接Taotoken多模型API的配置教程
  • Unity图表性能优化：从折线图到饼图的底层实现与避坑指南
  • 如何3分钟掌握AI智能填充：Fillinger终极实战指南
  • 大模型部署困境破局：Qwen模型ONNX格式转换与多平台部署实战
  • 新一代高性能SAR舰船智能检测数据集SSDD：从集中到分散的渐进式检测范式革新
  • 企业内训系统集成Taotoken实现多模型AI助教与可控的交互成本
  • 新手开发者首次接触 Taotoken 控制台的功能导览与核心操作
  • MATLAB机器人工具箱：从零到精通的机器人开发全攻略
  • Arduino UNO R3引脚图详解与供电方案选择：从USB到外接电源的避坑指南
  • Winhance中文版终极指南：3步让你的Windows飞起来
  • 注意力机制的幕后：它到底转化了什么？输入、输出与词向量的类比
  • 《纳瓦尔宝典》幸福篇精读：程序员如何在敲码之余获得内心的平静与幸福
  • 渐变不自然？曝光过曝？色阶断裂？Midjourney渐变风格全流程调优手册，30分钟重塑视觉一致性
  • SELinux报错排查指南：从AVC拒绝日志到精准修复
  • SDL2初始化函数全解析：从SDL_Init到SDL_Quit，你的游戏引擎第一行代码该怎么写？
  • 在无MMU的RISC-V MCU上移植Linux 6.10内核：基于HPM6360的实践指南
  • 如何高效配置CharacterAI Python API：完整使用指南与最佳实践
  • 鸿蒙 PC：从“用户点击”到“AI 调度”
  • Python自动化CAD处理终极指南：用ezdxf库实现DXF文件高效操作
  • 2026 最新claude-code 实用技巧指南 看这一篇就够了
  • 3步实现Adobe全家桶完整激活：终极破解方案详解
  • 如何永久保存你的微信聊天记录：WeChatMsg完整解决方案指南
  • vSphere 7.0环境搭建：除了安装vCSA，这些后期配置（许可证、告警、备份）你做了吗？
  • ULINK调试器独立编程HEX文件全指南
  • 高云Arora-V 60K FPGA图像开发板：从硬件架构到实时视觉系统实战
  • 3个技巧彻底掌握泰坦之旅装备管理神器
  • 5分钟搞定Windows 11臃肿问题！Win11Debloat让你的电脑重获新生
  • 终极Windows系统优化指南：如何使用Winhance中文版快速提升电脑性能
  • 从任务栏消失到界面混乱：如何用ExplorerPatcher拯救你的Windows 11体验