前言
申明兩個(gè)基本函數(shù)
boolean isNumeric(String num);
int compareTwoBigInt(String num1, String num2);
/**
*判斷某字符串是否為大整數(shù)
*/
public static boolean isNumeric(String num){
if(num == null || num.length() == 0) return false;
if(num.length() > 1 && num.charAt(0) == '0') return false;//長(zhǎng)度大于1時(shí)尤莺，首位為0，返回false
Pattern pattern = Pattern.compile("[0-9]*");
return pattern.matcher(num).matches();
}
/**
* 判斷兩個(gè)有效大整數(shù)的大小
* @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;
}
加法
/**
* 大整數(shù)【帶符號(hào)】求和
* @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;
//獲取被加數(shù)生棍、加數(shù)的符號(hào)
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 += "*";
//輸入合法性檢測(cè)
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
String res = "";
String flag = "";
//比較去符號(hào)后num1和num2大小
//-1: num1 < num2
// 0: num1 = num2
//+1: num1 > num2
int cmp = compareTwoBigInt(num1, num2);
//被加數(shù)颤霎、加數(shù)同為正數(shù)或者同為負(fù)數(shù)
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 ? "-" : "";//被加數(shù)、加數(shù)同為正數(shù)時(shí)涂滴，符號(hào)為正友酱，否則為負(fù)
int i = num1.length() - 1, j = num2.length() - 1;
int carry = 0, base = '0' * 2;//進(jìn)位、'0'的Ascii碼值的兩倍
//從低位開(kāi)始求和
for(; i >= 0 && j >= 0; i --, j --){
int sum = num1.charAt(i) + num2.charAt(j) - base + carry;
//計(jì)算進(jìn)位柔纵、低位值
if(sum >= 10){
carry = 1;
sum -= 10;
}
else carry = 0;
res = sum + res;
}
//num1>num2,處理num1還沒(méi)求和的高位值
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最高位求和后有無(wú)進(jìn)位
}
//被加數(shù)缔杉、加數(shù)一正一負(fù)
else{
if(cmp == 0) return "0";//若二者相等，返回結(jié)果0
else if(cmp > 0){
if(sign.equals("-+") || sign.equals("-*")) flag = "-";//去符號(hào)后num1>num2時(shí)首量，num1為負(fù)數(shù)
}
else{
String t = num1;
num1 = num2;
num2 = t;
if(sign.equals("+-") || sign.equals("*-")) flag = "-";//去符號(hào)后num1<num2時(shí)壮吩，num2為負(fù)數(shù)
}
int borrow = 0, i, j;//借位
//從低位開(kāi)始求差
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;
}
減法
/**
* 大整數(shù)【帶符號(hào)】求差
* @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";
//獲取被減數(shù)、減數(shù)的符號(hào)
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 += "*";
//輸入合法性檢測(cè)
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
String res = "";
String flag = "";
int cmp = compareTwoBigInt(num1, num2);//比較去符號(hào)后num1和num2的大小
//System.out.println("cmp = " + cmp + "\tnum1 = " + num1 + "\tnum2 = " + num2);
//被減數(shù)和減數(shù)正負(fù)相反觉啊，則轉(zhuǎn)化為加法問(wèn)題
if(sign.equals("+-") || sign.equals("*-") || sign.equals("-+") || sign.equals("-*")){
if(sign.equals("+-") || sign.equals("*-")) flag = "";
else flag = "-";
//num1<num2時(shí)交換二者的值
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;
}
//被減數(shù)拣宏、減數(shù)同正同負(fù)
else{
//判斷num1與num2的大小,再根據(jù)sign確認(rèn)最終符號(hào)位
//若num1小于num2， 交換二者且符號(hào)位僅當(dāng)num1杠人、num2的符號(hào)位均為正時(shí)為負(fù)
if(cmp == 0) return "0";
if(cmp < 0){
String t = num1;
num1 = num2;
num2 = t;
if(!sign.equals("--")) flag = "-";//num1<num2時(shí)勋乾，num1、num2同負(fù)時(shí)結(jié)果為正嗡善；否則結(jié)果為負(fù)
}
//若num1>num2辑莫， 符號(hào)位僅當(dāng)原num1、num2的符號(hào)位均為負(fù)時(shí)為負(fù)
else{
if(sign.equals("--")) flag = "-";
}
int borrow = 0, i, j;//借位
//低位開(kāi)始求差
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);
}
乘法
/**
* 大整數(shù)【帶符號(hào)】求積
* @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 += "*";
//輸入合法性檢測(cè)
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
//獲取符號(hào)位
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]得到的乘積為結(jié)果第i+j個(gè)位置的值
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;
//從低位開(kāi)始求進(jìn)位及低位對(duì)應(yīng)值
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;
}
//處理最高位的進(jìn)位
if(carry > 0) res = carry + res;
return flag + res;
}
除法:減法
/**
* 大整數(shù)【帶符號(hào)】求商
* @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 += "*";
//輸入合法性檢測(cè)
if(!isNumeric(num1) || !isNumeric(num2)) throw new IllegalArgumentException("illegal input");
//獲取符號(hào)位
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;
}
