前言
申明两个基本函数
boolean isNumeric(String num);
int compareTwoBigInt(String num1, String num2);
/**
*判断某字符串是否为大整数
*/
public static boolean isNumeric(String num){
if(num == null || num.length() == 0) return false;
if(num.length() > 1 && num.charAt(0) == '0') return false;//长度大于1时，首位为0，返回false
Pattern pattern = Pattern.compile("[0-9]*");
return pattern.matcher(num).matches();
}
/**
* 判断两个有效大整数的大小
* @param num1
* @param num2
* @return 1 if num1 > num2, or 0 if num1 = num2, or -1 if num1 < num2
*/
public static int compareTwoBigInt(String num1, String num2){
if(num1.length() > num2.length()) return 1;
if(num1.length() < num2.length()) return -1;
for(int i = 0; i < num1.length(); i ++){
if(num1.charAt(i) > num2.charAt(i)) return 1;
if(num1.charAt(i) < num2.charAt(i)) return -1;
}
return 0;
}
加法
/**
* 大整数【带符号】求和
* @param num1
* @param num2
* @return
*/
public static String Add(String num1, String num2) {
if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) return null;
//获取被加数、加数的符号
String sign = "";
if(num1.charAt(0) == '+' || num1.charAt(0) == '-'){
sign = sign + num1.charAt(0);
num1 = num1.substring(1);
}
else sign = "*";
if(num2.charAt(0) == '+' || num2.charAt(0) == '-'){
sign = sign + num2.charAt(0);
num2 = num2.substring(1);
}
else sign += "*";
//输入合法性检测
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
String res = "";
String flag = "";
//比较去符号后num1和num2大小
//-1: num1 < num2
// 0: num1 = num2
//+1: num1 > num2
int cmp = compareTwoBigInt(num1, num2);
//被加数、加数同为正数或者同为负数
if(sign.equals("++") || sign.equals("+*") || sign.equals("*+") || sign.equals("**") || sign.equals("--")){
//若num1<num2,交换二者的值
//System.out.println("num1 = " + num1 + "\tnum2 = " + num2 + "\tcmp = " + cmp);
if(cmp < 0){
String t = num1;
num1 = num2;
num2 = t;
}
//System.out.println("num1 = " + num1 + "\tnum2 = " + num2 + "\tcmp = " + cmp);
flag = sign.equals("--") == true ? "-" : "";//被加数、加数同为正数时，符号为正，否则为负
int i = num1.length() - 1, j = num2.length() - 1;
int carry = 0, base = '0' * 2;//进位、'0'的Ascii码值的两倍
//从低位开始求和
for(; i >= 0 && j >= 0; i --, j --){
int sum = num1.charAt(i) + num2.charAt(j) - base + carry;
//计算进位、低位值
if(sum >= 10){
carry = 1;
sum -= 10;
}
else carry = 0;
res = sum + res;
}
//num1>num2,处理num1还没求和的高位值
for(; i >= 0; i --){
int sum = num1.charAt(i) - '0' + carry;
if(sum >= 10){
carry = 1;
sum -= 10;
}
else carry = 0;
res = sum + res;
//System.out.println("res = " + res);
}
if(carry >= 1) res = carry + res;//判断num1最高位求和后有无进位
}
//被加数、加数一正一负
else{
if(cmp == 0) return "0";//若二者相等，返回结果0
else if(cmp > 0){
if(sign.equals("-+") || sign.equals("-*")) flag = "-";//去符号后num1>num2时，num1为负数
}
else{
String t = num1;
num1 = num2;
num2 = t;
if(sign.equals("+-") || sign.equals("*-")) flag = "-";//去符号后num1<num2时，num2为负数
}
int borrow = 0, i, j;//借位
//从低位开始求差
for(i = num1.length() - 1, j = num2.length() - 1; i >= 0 && j >= 0; i --, j --){
int left = num1.charAt(i) - num2.charAt(j) + borrow;
//更新借位、低位值
if(left < 0){
borrow = -1;
left += 10;
}
else borrow = 0;
res = left + res;
//System.out.println("left = " + left + "\tborrow = " + borrow + "\ti = " + i + "\tj = " + j + "\tres = " + res);
}
//保证了num1 > num2，处理num1还未求差的高位
for(; i >=0; i --){
int left = num1.charAt(i) - '0' + borrow;
if(left < 0){
borrow = -1;
left += 10;
}
else borrow = 0;
res = left + res;
}
}
return flag + res;
}
减法
/**
* 大整数【带符号】求差
* @param num1
* @param num2
*/
public static String Minus(String num1,String num2){
if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) return "-1";
//获取被减数、减数的符号
String sign = "";
if(num1.charAt(0) == '+' || num1.charAt(0) == '-'){
sign = sign + num1.charAt(0);
num1 = num1.substring(1);
}
else sign = "*";
if(num2.charAt(0) == '+' || num2.charAt(0) == '-'){
sign = sign + num2.charAt(0);
num2 = num2.substring(1);
}
else sign += "*";
//输入合法性检测
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
String res = "";
String flag = "";
int cmp = compareTwoBigInt(num1, num2);//比较去符号后num1和num2的大小
//System.out.println("cmp = " + cmp + "\tnum1 = " + num1 + "\tnum2 = " + num2);
//被减数和减数正负相反，则转化为加法问题
if(sign.equals("+-") || sign.equals("*-") || sign.equals("-+") || sign.equals("-*")){
if(sign.equals("+-") || sign.equals("*-")) flag = "";
else flag = "-";
//num1<num2时交换二者的值
if(cmp < 0){
String t = num1;
num1 = num2;
num2 = t;
}
int i = num1.length() - 1, j = num2.length() - 1, carry = 0, base = '0' * 2;
for(; i >= 0 && j >= 0; i --, j --){
int sum = num1.charAt(i) + num2.charAt(j) - base + carry;
if(sum >= 10){
carry = 1;
sum -= 10;
}
else carry = 0;
res = sum + res;
}
for(; i >= 0; i --){
int sum = num1.charAt(i) - '0' + carry;
if(sum >= 10){
carry = 1;
sum -= 10;
}
else carry = 0;
res = sum + res;
}
if(carry >= 1) res = carry + res;
}
//被减数、减数同正同负
else{
//判断num1与num2的大小,再根据sign确认最终符号位
//若num1小于num2， 交换二者且符号位仅当num1、num2的符号位均为正时为负
if(cmp == 0) return "0";
if(cmp < 0){
String t = num1;
num1 = num2;
num2 = t;
if(!sign.equals("--")) flag = "-";//num1<num2时，num1、num2同负时结果为正；否则结果为负
}
//若num1>num2， 符号位仅当原num1、num2的符号位均为负时为负
else{
if(sign.equals("--")) flag = "-";
}
int borrow = 0, i, j;//借位
//低位开始求差
for(i = num1.length() - 1, j = num2.length() - 1; i >= 0 && j >= 0; i --, j --){
int left = num1.charAt(i) - num2.charAt(j) + borrow;
if(left < 0){
borrow = -1;
left += 10;
}
else borrow = 0;
res = left + res;
}
//保证了num1 > num2
for(; i >=0; i --){
int left = num1.charAt(i) - '0' + borrow;
if(left < 0){
borrow = -1;
left += 10;
}
else borrow = 0;
res = left + res;
}
}
int i = 0;
for(; i < res.length(); i ++) if(res.charAt(i) != '0') break;
return flag + res.substring(i);
}
乘法
/**
* 大整数【带符号】求积
* @param num1
* @param num2
* @return
*/
public static String Multiply(String num1, String num2){
if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) return null;
String sign = "";
if(num1.charAt(0) == '+' || num1.charAt(0) == '-'){
sign = sign + num1.charAt(0);
num1 = num1.substring(1);
}
else sign = "*";
if(num2.charAt(0) == '+' || num2.charAt(0) == '-'){
sign = sign + num2.charAt(0);
num2 = num2.substring(1);
}
else sign += "*";
//输入合法性检测
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
//获取符号位
String flag = "", res = "";
if(sign.equals("+-") || sign.equals("-+") || sign.equals("-*") || sign.equals("*-")) flag = "-";
if(num1.equals("0") || num2.equals("0")) return "0";
if(num1.equals("1")) return num2;
if(num2.equals("1")) return num1;
int[] multiply = new int[num1.length() + num2.length() - 1];
int base = '0';
//num1[i] * num2[j]得到的乘积为结果第i+j个位置的值
for(int i = 0; i < num1.length(); i++)
for(int j = 0; j < num2.length(); j ++)
multiply[i + j] += (num1.charAt(i) - base) * (num2.charAt(j) - base);
int carry = 0;
//从低位开始求进位及低位对应值
for(int i = num1.length() + num2.length() - 2; i >= 0; i --){
multiply[i] += carry;
carry = multiply[i] / 10;
multiply[i] %= 10;
res = multiply[i] + res;
}
//处理最高位的进位
if(carry > 0) res = carry + res;
return flag + res;
}
除法:减法
/**
* 大整数【带符号】求商
* @param num1
* @param num2
*/
public static String Divide(String num1,String num2){
if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) return null;
String sign = "";
if(num1.charAt(0) == '+' || num1.charAt(0) == '-'){
sign = sign + num1.charAt(0);
num1 = num1.substring(1);
}
else sign = "*";
if(num2.charAt(0) == '+' || num2.charAt(0) == '-'){
sign = sign + num2.charAt(0);
num2 = num2.substring(1);
}
else sign += "*";
//输入合法性检测
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
//获取符号位
if(num2.charAt(0) == '0') throw new IllegalArgumentException("illegal input");
int cmp = compareTwoBigInt(num1, num2);
if(num1.charAt(0) == '0' || cmp < 0) return "0";
if(cmp == 0) return "1";
String flag = "";
if(sign.equals("+-") || sign.equals("-+") || sign.equals("-*") || sign.equals("*-")) flag = "-";
int res = 0;
String result = "0";
while(num1.charAt(0) != '-' && !num1.equals("0")){
num1 = Minus(num1, num2);
if(res + 1 < Integer.MAX_VALUE) res += 1;
else{
result = Add(result, Integer.toString(res));
res = 1;
}
}
if(num1.charAt(0) == '-') res -= 1;
System.out.println("res = " + res);
result = Add(result, Integer.toString(res));
return result;
}
