自己写Java大整数《1》表示和加减
自己写Java大整数《一》表示和加减
比较绝对大小
取负值
上周粗略计划自己写Java下的大整数运算。
后来仔细想想其实自己动手写大整数运算有1好2不好。2个不好分别是:
1,肯定没有Java内置的BigInteger安全快速;2,自己写的大数包只能自己使用,不具有可移植性。
但是还有一个大大的好处就是
1,促进自己学习和弄清楚大数运算的机制,对自己进步有帮助。
所以我决定开始继续写下去。
开始在上篇计划中,我大概列出了会遇到的问题。下面我首先解决大数的表示、绝对值的比较大小、取负值和加减法运算。
后面我会不断添加乘法,除法,mod运算等。
进制问题
为了避免进制的转换,使用十进制的倍数。
int 类型的数十-2^31-2^31-1 大约是9.33位数的十进制
所以使用int表示一个位,每位是10^9。也满足两个小于10^9的和
在int 可表示的范围之内
long类型的数是-2^63到 2^63-1大约是18.965十进制
相乘正好落到long类型里。
我这里选择一个int的数组表示大数,低位的数组表示大数的高位。如图所示
private int[] digits;也就是digits[0] 表示最高位,digits[digits.length] 表示最低位
符号问题
这里使用专门的一个整数表示正负号。-1表示负数;0表示零;1表示正数
private int sign;
初始化问题
使用int的sign和一个数组初始化大整数如下
public DecimalBig(int sign, int[] digits) { for(int i=0; i<digits.length; i++){ if (digits[i]<0 || digits[i]>Radix) throw new IllegalArgumentException("digit " + digits[i] + " out of range!"); } this.sign = sign; this.digits = digits; }
比较绝对大小
由于在带符号的加法中需要分析不同符号加法事谁减谁的问题,需要比较绝对值的大小。如下
我这里只是直接的写了一个,应该可以大大的优化。首先比较长度,长度相同则诸位比较
public int AbsCompare(DecimalBig that) { int result =0; if (this.digits.length>that.digits.length) result=1; else{ if (this.digits.length<that.digits.length) result=-1; else{ if(this.digits.length==0) result=0; else{ int i=0; while(i<this.digits.length&&this.digits[i]==that.digits[i]) i++; if(i==this.digits.length) result=0; else{ if (this.digits[i]>that.digits[i]) result=1; else result=-1; } } } } return result; }
取负值
直接对sign取相反数-sign
public DecimalBig negate() { return new DecimalBig(-this.sign, this.digits); }
加减法
对于加法减法首先实现一串数组的加减法。其中加法和经典的十进制算法基本一致,这里要特别注意进位问题。
减法要特别注意借位和去零的问题。
见下面代码
/** * */ /** * @author Xue * at 2014.7.20 */ public class DecimalBig { /* * 采用10^9进制的计算 */ final static int Radix = 1000000000; /* * 美俄基数十进制的长度 */ final static int Radix_Dicimal_length=9; /* * 每一个大整数都表示成一串int类型的数 */ private int[] digits; /* * 符号,其中-1代表负数,0代表0,1代表正数 */ private int sign; /* * 构造函数,这里选择的是小头高位,大头低位的方法存储的数据 */ public DecimalBig(int sign, int[] digits) { for(int i=0; i<digits.length; i++){ if (digits[i]<0 || digits[i]>Radix) throw new IllegalArgumentException("digit " + digits[i] + " out of range!"); } this.sign = sign; this.digits = digits; } private static int[] ONE={1}; public static final DecimalBig Zero=new DecimalBig(0, new int[0]); public static final DecimalBig One=new DecimalBig(1, ONE); /* * 绝对值大小的比较,this 大则返回1,小返回1,相等返回0 */ public int AbsCompare(DecimalBig that) { int result =0; if (this.digits.length>that.digits.length) result=1; else{ if (this.digits.length<that.digits.length) result=-1; else{ if(this.digits.length==0) result=0; else{ int i=0; while(i<this.digits.length&&this.digits[i]==that.digits[i]) i++; if(i==this.digits.length) result=0; else{ if (this.digits[i]>that.digits[i]) result=1; else result=-1; } } } } return result; } /* * 反转符号, */ public DecimalBig negate() { return new DecimalBig(-this.sign, this.digits); } /* * 返回绝对值; */ public DecimalBig abs() { return this.sign>=0?this:this.negate(); } /* * 加法, */ public DecimalBig Add(DecimalBig that) { //this 是 0 if (this.sign==0) return that; //that 是0 if (that.sign==0) return this; //相同符号 if (that.sign==this.sign) return new DecimalBig(this.sign, Add(this.digits,that.digits)); //不同符号 if (this.AbsCompare(that)==0) return Zero; if (this.AbsCompare(that)==1) return new DecimalBig(this.sign, Substract(this.digits,that.digits)); return new DecimalBig(that.sign, Substract(that.digits,this.digits)); } /* * 减法 */ public DecimalBig substract(DecimalBig that) { //this 是 0 if (this.sign==0) return that.negate(); //that 是0 if (that.sign==0) return this; //不同符号 if (that.sign!=this.sign) return new DecimalBig(this.sign, Add(this.digits,that.digits)); //相同符号 if (this.AbsCompare(that)==0) return Zero; if (this.AbsCompare(that)==1) return new DecimalBig(this.sign, Substract(this.digits,that.digits)); return new DecimalBig(that.sign, Substract(that.digits,this.digits)); } /* * 两个数组的加法 */ public static int[] Add(int[] x, int[] val) { int[] MaxBig, MinBig; /* * 拷贝较长的数到MaxBig较短的数到MinBig */ if (x.length<val.length) { MaxBig=x; MinBig=val; }else { MaxBig=val; MinBig=x; } /* * 建立要返回的数组addresult;进位制记为carry */ int[] addresult = new int[MaxBig.length]; int carry=0; /* * 简单的进位加法 */ for (int i=MaxBig.length-1;i>=0;i--) { int extadd=0; if (i>MaxBig.length-MinBig.length-1) extadd=MinBig[i-(MaxBig.length-MinBig.length)]; else extadd=0; int DigitSum=MaxBig[i]+extadd+carry; addresult[i]=DigitSum%Radix; carry=DigitSum/Radix; } /* * 最高位哟啊是有进位的话,拉长一位 */ if (carry==1) { int[] temp = new int[MaxBig.length + 1]; System.arraycopy(addresult, 0, temp, 1, MaxBig.length); temp[0] = carry; addresult = temp; } return addresult; } /* * 两个数组的减法; */ public static int[] Substract(int[] Big, int[] little) { /* * 建立要返回的数组addresult;进位制记为carry */ int[] subresult = new int[Big.length]; int carry=0; /* * 简单的进位加法 */ for (int i=Big.length-1;i>=0;i--) { int extsub=0; if (i>Big.length-little.length-1) extsub=little[i-(Big.length-little.length)]; else extsub=0; int Digitsub=Big[i]-extsub-carry; if(Digitsub<0){ subresult[i]=Digitsub+Radix; carry=1; } else{ subresult[i]=Digitsub; carry=0; } } /* * 去掉高位的零 */ int i=0; while(i<subresult.length&&subresult[i]==0) i++; //截取非零项 int[] temp = new int[subresult.length-i]; System.arraycopy(subresult, i, temp, 0, subresult.length-i); subresult = temp; return subresult; } public static void main(String arg[]) { int[] a={573450000, 5, 2, 573450000}; int[] b={573450000, 5, 2, 5}; DecimalBig c = new DecimalBig(-1,a); DecimalBig d = new DecimalBig(1,b); System.out.println(Add(c.digits, d.digits)[4]); System.out.println(c.AbsCompare(d)); System.out.println(c.Add(d).sign); System.out.println(c.Add(d).digits.length); System.out.println(c.Add(d).digits[0]); System.out.println(c.Add(d).digits[1]); System.out.println(c.Add(d).digits[2]); System.out.println(c.Add(d).digits[3]); System.out.println(c.Add(d).digits[4]); } }