首页 > 代码库 > 大整数的加减乘除C++实现

大整数的加减乘除C++实现

大整数的乘法由于用分治法理解起来有点困难,就采用人的计算方法实现,大整数为string 类型,结果也为string类型。

大整数的除法采用先乘后减的方法,例如:

  665/20

  首先20*10=200;然后665去减200,通过循环计入减了3次,则结果记入3*10=30;然后20*1=20,上次减了之后还剩65,65-20,又减了3次,所以结果记入30+3*1=33;最后还剩5,比20小,则余数为5。

大整数的加法减法和人工打草稿过程类似,不做详细分析。实现代码仅供参考:

  1 #include<iostream>
  2 #include<string>
  3 using namespace std;
  4 
  5 const int MAX = 256;
  6 int a_pos , b_pos ;
  7 int a_len, b_len; 
  8 string remain="0"; //保存除法的余数
  9 
 10 string def_multiply(string a, string b) //默认的乘法(正正)
 11 {
 12     char result[MAX] = { 0 };
 13     int length;
 14     a_len = a.length(), b_len = b.length();
 15     string result_str = "";
 16     int flag = 0,sum=0;
 17     int top;
 18     for (int i1 = 0, a_pos = a_len - 1; i1 < a_len; i1++, a_pos--)
 19     {
 20         for (int i2 = 0, b_pos = b_len - 1; i2 < b_len; i2++, b_pos--)
 21         {
 22             top = i1 + i2;
 23             sum = result[top] + (a[a_pos] - 48)*(b[b_pos] - 48) + flag;
 24             result[top] = sum % 10;
 25             flag = sum / 10;
 26         }
 27         if (flag>0)
 28         {
 29             top++;
 30             result[top] = result[top]+flag % 10;
 31             flag = flag / 10;
 32         }
 33         length = top;
 34     }
 35     for (; length >= 0; length--)
 36     {
 37         result_str+= result[length]+48;
 38     }
 39     return result_str;
 40 }
 41 
 42 string def_add(string a, string b)//默认加法(正正)
 43 {
 44     string result_str = "";
 45     char result[MAX] = { 0 };
 46     int flag = 0, sum = 0;
 47     int length;
 48     a_len = a.length(), b_len = b.length();
 49     int  len = (a_len > b_len ? a_len : b_len);
 50     length = len-1;
 51     for (int i = 0, b_pos = b_len - 1, a_pos = a_len - 1; i < len; i++, a_pos--,b_pos--)
 52     {
 53         if (b_pos < 0)
 54         {
 55             sum = a[a_pos] - 48 + flag;
 56             result[i] = sum%10;
 57             flag = sum / 10;
 58         }
 59         else if (a_pos < 0)
 60         {
 61             sum = b[b_pos] - 48 + flag;
 62             result[i] = sum % 10;
 63             flag = sum / 10;
 64         }
 65         else
 66         {
 67             sum = a[a_pos] + b[b_pos] - 96+flag;
 68             result[i] = sum % 10;
 69             flag = sum / 10;
 70         }
 71     }
 72     if (flag > 0)
 73     {
 74         length++;
 75         result[len]=flag;
 76     }
 77     for (; length >= 0; length--)
 78     {
 79         result_str += result[length] + 48;
 80     }
 81     return result_str;
 82 }
 83 
 84 
 85 string def_subtract(string a, string b) //默认减法(大的正减小的正数)
 86 {
 87     char result[MAX] = { 0 };
 88     a_len = a.length(), b_len = b.length();
 89     int flag = 0;
 90     int i = 0;
 91     string str = "";
 92     for (b_pos = b_len - 1, a_pos = a_len - 1; i < b_len; i++, a_pos--, b_pos--)
 93     {
 94         if (a[a_pos] < b[b_pos])
 95         {
 96             result[i] = a[a_pos] + 10 - b[b_pos];
 97             a[a_pos - 1]-=1;
 98         }
 99         else
100         {
101             result[i] = a[a_pos]  - b[b_pos];
102         }
103 
104     }
105     for (i = a_len - b_len - 1; i >= 0; i--)
106     {
107         if (a[i] < 0)
108         {
109             a[i - 1]--;
110             result[a_len - i - 1] = a[i] - 38;
111         }
112         else{ result[a_len - i - 1] = a[i] - 48; }
113     }
114     
115     for (i=a_len-1; i >= 0; i--)
116     {
117         str += result[i] + 48; 
118     }
119     int j = 0;
120     while (str[j] == 0&&j!=str.length())
121     {
122         j++;
123     }
124     if (j != 0)str.erase(0, j);
125     if (str.length()==0)str = "0";
126     return str;
127 }
128 
129 string multiply(string a, string b)  //整数的乘法
130 {
131     string str;
132     if (a[0] == -&&b[0] != -)
133     {
134         a = a.substr(1);
135         str ="-"+ def_multiply(a, b);
136         return str;
137     }
138     else if (b[0] == -&&a[0] != -)
139     {
140         b = b.substr(1);
141         str = "-" + def_multiply(a, b);
142         return str;
143     }
144     else if (b[0] == -&&a[0] == -)
145     {
146         a = a.substr(1);
147         b = b.substr(1);        
148         return def_multiply(a, b);
149     }
150     else
151     {
152         return def_multiply(a, b);
153     }
154 }
155 
156 string subtract(string a, string b) //整数的减法
157 {
158     string str;
159     if (a[0] == -&&b[0] != -)
160     {
161         a = a.substr(1);
162         str = "-" + def_add(a, b);
163         return str;
164     }
165     else if (b[0] == -&&a[0] != -)
166     {
167         b = b.substr(1);
168         str = def_add(a, b);
169         return str;
170     }
171     else if (b[0] == -&&a[0] == -)
172     {
173         a = a.substr(1);
174         b = b.substr(1);
175         return subtract(b, a);
176     }
177     else
178     {
179         if (a.length() > b.length() || (a.length() == b.length() && a >= b))
180         {
181             str=def_subtract(a, b);
182             return str;
183         }
184         else
185         {
186             str = "-" + def_subtract(b, a);
187             return str;
188         }
189     }
190 }
191 
192 string add(string a, string b)//整数的加法
193 {
194     string str;
195     if (a[0] == -&&b[0] != -)
196     {
197         a = a.substr(1);        
198         return subtract(b, a);
199     }
200     else if (b[0] == -&&a[0] != -)
201     {
202         b = b.substr(1);
203         return subtract(a, b);
204     }
205     else if (b[0] == -&&a[0] == -)
206     {
207         a = a.substr(1);
208         b = b.substr(1);
209         str="-" + def_add(a, b);
210         return str;
211     }
212     else
213     {
214         return def_add(a, b);
215     }
216 }
217 
218 string def_divide(string a, string b) //默认的除法(正的除正的)
219 {
220     int length,j=0;
221     string s, b2,sum="0", temp="";
222     a_len = a.length(), b_len = b.length();
223     if (a == b)
224         return "1";
225     if (a_len > b_len)
226     {    
227         s = a;
228         length = a_len - b_len;
229         for (; length >= 0; length--)
230         {
231             b2 = b;
232             for (int i = 0; i < length; i++)
233                 b2 = b2 + 0;
234             
235             while (s[0] != -)
236             {        
237                 s = subtract(s, b2);
238                 j++ ;
239             }
240             s = add(s, b2);
241             char ch = j + 48-1;
242             temp += ch;
243             for (int i = 0; i < length; i++)
244                 temp = temp + "0";
245             sum = def_add(sum,temp);
246             temp = "",j=0;
247         }
248         remain = s;
249         return sum;
250     }
251     else if (a_len == b_len  && a > b)
252     {
253         s = a;
254         sum = (a[0] - 48) / (b[0] - 48)+48;    
255         for (int i = 0; i < (a[0] - 48) / (b[0] - 48); i++)
256         {
257             s = def_subtract(s, b);
258         }
259         return sum;
260     }
261     else
262     {
263         return "0";
264     }
265 }
266 
267 string divide(string a, string b) //整数的除法
268 {
269     string str;
270     if (a[0] == -&&b[0] != -)
271     {
272         a = a.substr(1);
273         str="-"+def_divide(a, b);
274         remain = "-" + remain;
275         return str;
276     }
277     else if (b[0] == -&&a[0] != -)
278     {
279         b = b.substr(1);
280         return "-" + def_divide(a, b);
281     }
282     else if (b[0] == -&&a[0] == -)
283     {
284         a = a.substr(1);
285         b = b.substr(1);
286         str = def_divide(a, b);
287         remain = "-" + remain;
288         return str;
289     }
290     else
291     {
292         return def_divide(a, b);
293     }
294 }

写一个main函数测试:

 1 #include<iostream>
 2 #include"BigNum.h"
 3 using namespace std;
 4 int main()
 5 {
 6     string a;
 7     string b;
 8     cin >> a >> b;
 9     cout << a << "+" << b << "=" << add(a, b) << endl;
10     cin >> a >> b;
11     cout << a << "-" << b << "=" << subtract(a, b) << endl;
12     cin >> a >> b;
13     cout << a << "*" << b << "=" << multiply(a, b) << endl;
14     cin >> a >> b;
15     cout << a<<"/"<<b<<"="<<divide(a, b) <<" remainder is " << remain<< endl;
16     system("pause");
17     return 0;
18 }

技术分享

 

大整数的加减乘除C++实现