前些天做了份笔试题，最后一道题是写一个大数相乘的算法，太久没做题了，也没有草稿纸，脑子没动起来，笔就开始天马行空了，写到一半觉得不对劲了，很多东西没注意，估计凉了，静下心来，重新回顾下知识点，顺便重新做一下这道题：
参考：https://www.cnblogs.com/axclogo/p/5416510.html
点明一下（废话）：大家都知道，数据类型超过了计算机字长的界限就会出现数据溢出的情况，这种情况在数值较大时进行数字运算时很容易出现，防止数据溢出方法如下：
一、创建结构体，将溢出的数据转移到另一个变量中存储；
二、创建或设计一个存储器，将所有巨大的数值存储在这个存储器中，算法类似于时钟算法，满多少进一位。再设计一个取出器，将转换后的变量转换成巨大的数值，边转换边计算；
三、创建数组来按位数来存储数据；
而我下面要讲的是使用字符串、数组储存（有这么方便的东西为什么要去创建个结构体或者存储器呢？）
下面都是先上代码，也可以滑下去看思路
大数相加：
+ (NSString*)additionOfString:(NSString*)strOne AndString:(NSString*)strTwo{
NSMutableString *One = [NSMutableString stringWithFormat:@"%@",strOne ];
NSMutableString *Two = [NSMutableString stringWithFormat:@"%@",strTwo ];
NSInteger longerLength =0;
NSInteger t= 0;
intjin =0;
NSMutableString *strJ = [NSMutableString new];
NSMutableString *sum = [NSMutableString new];
// 位数少的用0补齐，使两个字符串位数相等
if(One.length> Two.length) {
t = One.length- Two.length;
for(NSInteger i =0;i < t;i++) {
[Two insertString:[NSString stringWithFormat:@"0"] atIndex:0];
}
}else if(One.length< Two.length) {
NSInteger t = Two.length- One.length;
for(NSInteger i =0;i < t;i++) {
[One insertString:[NSString stringWithFormat:@"0"] atIndex:0];
}
} else if (One.length== Two.length){
} else {
return @"您的输入有误！";
}
longerLength = One.length;
for(NSInteger i = longerLength -1; i >=0;i--) {
unichar onenum = [One characterAtIndex:i];
unichar twonum = [Two characterAtIndex:i];
int onum = [[NSString stringWithFormat:@"%c",onenum] intValue];
int tnum = [[NSString stringWithFormat:@"%c",twonum] intValue];
int c = onum + tnum + jin;
int current = c%10;
jin = c/10;
[strJ appendFormat:@"%d",current];
if(i ==0 && jin != 0) {
// 注意是不是最后一位，别把进位数丢了
[strJ appendFormat:@"%d",jin];
}
}
// 上面得到的是一个倒序字符串，需要变成正序
for(NSInteger i = strJ.length-1; i>=0;i--) {
unichar k = [strJ characterAtIndex:i];
[sum appendFormat:@"%c",k];
}
return sum;
}
思路：
要点：按位相加、进位数处理
大数以字符串传入，如“123456789999”加上“987654321”，为了方便计算，我们将这两个数，位数上补齐，得到：“123456789999”和“000987654321”，接下来就开始计算了。
个位加个位（9+1），得到一个数（10），记录进位数（1）和个位数（0），字符串拼接个位数（“0”）；然后十位和十位加上刚才的进位（9+2+1），得到一个数（12），记录进位数（1）和个位数（2），字符串拼接个位数（“02”）；后面类推，注意最后一位时把进位数补上就好；得到的是一个倒序字符串（“023444444421”），做一下正序操作（“124444444320”）就是我们想要的结果；
大数相乘：
这里大数相乘在最后一步用到大数相加，因为是自己写的，如果有更好的方法请指出：
+ (NSString*)mutiplyOfString:(NSString*)strOne AndString:(NSString*)strTwo{
NSMutableString *One = [NSMutableString stringWithFormat:@"%@",strOne ];
NSMutableString *Two = [NSMutableString stringWithFormat:@"%@",strTwo ];
int jin =0;
NSMutableString *strJ = [NSMutableString new];
NSMutableString *strT = [NSMutableString new]; // strJ的正序
NSString *sum = [NSString new];
NSMutableArray * strJArr = [NSMutableArray array];
for(NSInteger i = One.length-1; i >=0; i--) {
strJ = [NSMutableString new];
strT = [NSMutableString new];
jin =0;
unichar onenum= [One characterAtIndex:i];
for(NSInteger j = Two.length-1; j >=0; j--){
unichar twonum = [Two characterAtIndex:j];
int onum = [[NSString stringWithFormat:@"%c",onenum]intValue];
int tnum = [[NSString stringWithFormat:@"%c",twonum]intValue];
int c = onum * tnum +jin;
int z = c%10;
jin = c/10;
[strJ appendFormat:@"%d",z];
if(j ==0 && jin!=0) {
//是否最后一位
[strJ appendFormat:@"%d",jin];
}
// 正序操作
for(NSInteger a = strJ.length-1; a>=0;a--) {
unichar c = [strJ characterAtIndex:a];
[strT appendFormat:@"%c",c];
}
// 将strT放入数组，稍后加0后进行大数相加;
[strJArr addObject:strT];
}
if(strJArr.count==0){
return @"您的输入有误！";
}
for(NSInteger k =0; k < strJArr.count; k++){
NSMutableString*strP = strJArr[k];
// 高位数补0
for(NSInteger i = k;i >0;i--) {
[strP insertString:[NSString stringWithFormat:@"0"] atIndex:strP.length];
}
// 大数相加
sum = [BigNumberAdd additionOfString:sum AndString:strP];
}
return sum;
}
思路：
要点： 先一起来回顾一下，额，小学数学吧： 123 * 456 =（3+20+100）*456 = (3*456)+(20*456)+(100*456)
将大数A个位分别与大数B的每一位进行相乘（沿用大数相加的进位法），获得一个字符串（这里先叫做“个位字符串”），放入空数组中；将大数A十位分别与大数B的每一位进行相乘，得到下一个字符串（“十位字符串”），也放数组中；以此类推，最终得到一个字符串数组，然后给十位字符串乘10（就是后面插入一个“0”），百位字符串乘100（就是后面插入两个“0”）.... 得到一个新的字符串，最后用前面大数相加，将全部加起来即可。
步骤：
①拆位相乘
123 * 456
个位:ge = 3 * 456 => 3*6 + 3*5*10 + 3*4*100 => 1368
十位:shi = 2 * 456 => 2*6 + 2*5*10 + 2*4*100 => 912
百位:bai = 1 * 456 => 1*6 + 1*5*10 + 1*4*100 => 456
②加入数组得到： [ge,shi,bai];
③取出补零 （下面仅表示计算过程，因为是大数，实际上操作的是字符串，需用appendString补零）
ge = ge ( 1368 )
shi = shi * 10 ( 9120 )
bai = bai * 100 ( 45600 )
④大数相加
sum = ge + shi + bai ( 1368 + 9120 + 45600 = 57456)
就这样，思路其实还是挺简单。
