大整数的加减乘除

前言

申明两个基本函数
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;
}