实现两个大整数的相加,首先应该排除直接使用int和long long的方法,这些方法很容易溢出,这里为了方便(是否可以使用更精简的结构存储?)采用char来存储整数,整体思路如下:
-
对于整数n和m的字符串形式,按照数组索引的从大到小累加计算,直接将结果存储到对应的result字符串中,处理完毕后再将result逆序输出,需考虑0和-的输出情况;
-
考虑到有负号的情况,一开始就需要判断负号字符,这里将(-,-)和(+,+)统一当成相加操作然后都是负号的话在结尾补上负号,对于(+,-)和(-,+)统一处理成(大-小)的形式然后在结尾补负号;比如对于20-500转换成-(-20+500),对于-500+20准换成-(500-20)。
-
这里需要使用标志位nTake记录是否进位或借位;
-
还要考虑是否有异常字符出现,使用全局变量gInvalid记录有无异常。
1 #include<stdio.h>
2 #include<string.h>
3
4 #define Joshua_OJ
5
6 bool gInvalid = false;
7
8 // 0: equal, -1: n less m, 1: n bigger m
9 int AbsIsEqual(char* n, char* m, int n_start, int n_end, int m_start, int m_end)
10 {
11 if ((n_end - n_start) > (m_end - m_start)) return 1;
12 else if ((n_end - n_start) < (m_end - m_start)) return -1;
13 else
14 {
15 int i = n_start;
16 int j = m_start;
17 while (i <= n_end && j <= m_end)
18 {
19 if (n[i] > m[j]) return 1;
20 else if (n[i] < m[j]) return -1;
21 ++i;
22 ++j;
23 }
24 }
25 return 0;
26 }
27
28 void BigNumberAdd(char* n, char* m, char* result)
29 {
30 gInvalid = false;
31
32 if (n == NULL || m == NULL)
33 {
34 gInvalid = true;
35 return;
36 }
37
38 int n_index = strlen(n) - 1;
39 int m_index = strlen(m) - 1;
40
41 // 负数特别处理
42 int n_start = 0;
43 int m_start = 0;
44 int n_signed = 1;
45 int m_signed = 1;
46 if (n[0] == '-')
47 {
48 n_start = 1;
49 n_signed = -1;
50 }
51 if (m[0] == '-')
52 {
53 m_start = 1;
54 m_signed = -1;
55 }
56 // 如果只有一个负数,转换为大数减小数再取负号,这样方便异号借位相减
57 bool isResetPosNeg = false;
58 if (n_signed == 1 && m_signed == -1)
59 {
60 int tag = AbsIsEqual(n, m, n_start, n_index, m_start, m_index);
61 if (tag == -1)
62 {
63 n_signed = 0 - n_signed;
64 m_signed = 0 - m_signed;
65 isResetPosNeg = true;
66 }
67 else if (tag == 0)
68 {
69 result[0] = '0';
70 result[1] = '\0';
71 return;
72 }
73 }
74 else if (n_signed == -1 && m_signed == 1)
75 {
76 int tag = AbsIsEqual(n, m, n_start, n_index, m_start, m_index);
77 if (tag == 1)
78 {
79 n_signed = 0 - n_signed;
80 m_signed = 0 - m_signed;
81 isResetPosNeg = true;
82 }
83 else if (tag == 0)
84 {
85 result[0] = '0';
86 result[1] = '\0';
87 return;
88 }
89 }
90
91 int index = 0;
92 int nTake = 0;
93 while (n_index >= n_start || m_index >= m_start)
94 {
95 int op1, op2;
96 op1 = op2 = 0;
97
98 if (n_index >= n_start && (n[n_index] < '0' || n[n_index] > '9'))
99 {
100 gInvalid = true;
101 return;
102 }
103 if (m_index >= m_start && (m[m_index] < '0' || m[m_index] > '9'))
104 {
105 gInvalid = true;
106 return;
107 }
108
109 if (n_index >= n_start) op1 = n[n_index] - '0';
110 if (m_index >= m_start) op2 = m[m_index] - '0';
111 if (n_signed == 1 && m_signed == -1) op2 = m_signed * op2;
112 else if (m_signed == 1 && n_signed == -1) op1 = n_signed * op1;
113
114 int nSum = op1 + op2 + nTake;
115 if (nSum >= 10)
116 {
117 nSum -= 10;
118 result[index] = nSum + '0';
119 nTake = 1;
120 }
121 else if (nSum >= 0)
122 {
123 result[index] = nSum + '0';
124 nTake = 0;
125 }
126 else
127 {
128 nSum = 10 + nSum;
129 result[index] = nSum + '0';
130 nTake = -1;
131 }
132 --n_index;
133 --m_index;
134 ++index;
135 }
136
137 if (nTake == 1) result[index++] = nTake + '0';
138 else if (nTake == -1) result[index++] = '-';
139
140 if (isResetPosNeg) result[index++] = '-';
141 else if (n_signed == -1 && m_signed == -1) result[index++] = '-';
142
143 result[index] = '\0';
144 }
145
146 // 从后往前打印出这个数字,并忽略开头的0
147 void PrintNumber(char* number)
148 {
149 bool isBeginning0 = true;
150 int length = strlen(number);
151
152 for (int i = length - 1; i >= 0; --i)
153 {
154 if (i == length - 1 && number[i] == '-')
155 {
156 printf("%c", '-');
157 continue;
158 }
159
160 if (isBeginning0 && number[i] != '0')
161 {
162 isBeginning0 = false;
163 }
164
165 if (!isBeginning0)
166 {
167 printf("%c", number[i]);
168 }
169 else
170 {
171 if (i == 0) printf("%c", '0');
172 }
173 }
174 }
175
176 int main(void)
177 {
178 #ifdef Joshua_OJ
179 freopen("in.txt", "r", stdin);
180 #endif
181 int num;
182 char n[10000];
183 char m[10000];
184 char result[10002];
185
186 scanf("%d", &num);
187 while (num--)
188 {
189 scanf("%s %s", n, m);
190 BigNumberAdd(n, m, result);
191 if (gInvalid)
192 {
193 printf("%s\n", "invalid number");
194 continue;
195 }
196 PrintNumber(result);
197 printf("\n");
198 }
199
200 #ifdef Joshua_OJ
201 fclose(stdin);
202 #endif
203
204 return 0;
205 }
输入第一个数表示有多少组数据,对于无效数据需要输出invalid number
Input:
15
200 -22
22 -200
-200 22
-22 200
0 0
000 000
-111 -111
-50 50
50 -50
-333 -333
222 -100
222.222 222
123222222222456 89701234562222222
11111111111111111 11111111111111100
9999999999999999999999999999999999999999999999999999999 9999999999999999999999999999999999999999999999999999999
Output:
178
-178
-178
178
0
0
-222
0
0
-666
122
invalid number
89824456784444678
22222222222222211
19999999999999999999999999999999999999999999999999999998
原文链接: https://www.cnblogs.com/JoshuaMK/p/big_int_add.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/230724
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!