昨天笔试,遇到这么一个问题:如果系统要使用超大整数(超过long长度范围),请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数加法运算)。
其实这个问题很好解决,超大整数可以直接使用String来存储。对于两个String存储的超大整数的相加,先比较二者长度,在短的那个前面补0,使两个String一样长。
然后从尾部开始,挨个取数,相加并进位即可。代码如下:
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
| public String numAdd(String a,String b){ String str=""; int lenA=a.length(); int lenB=b.length(); int maxLen=lenA>lenB?lenA:lenB; int minLen=lenA<lenB?lenA:lenB; StringBuilder sb=new StringBuilder(); for(int i=0;i<maxLen-minLen;i++){ sb.append("0"); } if(lenA==minLen){ a=sb.append(a).toString(); } else{ b=sb.append(b).toString(); }
sb=new StringBuilder(); int tempA,tempB,result; int sc=0; for(int i=maxLen-1;i>=0;i--){ tempA=Integer.valueOf(a.charAt(i)+""); tempB=Integer.valueOf(b.charAt(i)+""); result=tempA+tempB+sc; sc=result/10; result=result%10; sb.append(result); } if(sc==1){ sb.append(sb); } str=sb.reverse().toString(); return str; }
|