bigint.java

大整数计算器

package 大整数计算器;

public class BigINT {
    private int Numbers[];

    private boolean PlusMinus;

    BigINT(StringBuffer Number, boolean PlusMinus) {
        Numbers = new int[Number.length()];
        for (int i = 1; i <= Number.length(); i++) {
            Numbers[i - 1] = toINT(Number.charAt(Number.length() - i));
        }
        this.PlusMinus = PlusMinus;

    }

    BigINT(int Numbers[], boolean PlusMinus) {
        this.Numbers = Numbers;
        this.PlusMinus = PlusMinus;
    }

    public int[] Numbers() {
        return Numbers;
    }

    public boolean PlusMinus() {
        return PlusMinus;
    }

    public BigINT Minus() {
        PlusMinus = !PlusMinus;
        return this;
    }

    private int toINT(char c) {
        int result = 0;
        switch (c) {
        case '1':
            result = 1;
            break;
        case '2':
            result = 2;
            break;
        case '3':
            result = 3;
            break;
        case '4':
            result = 4;
            break;
        case '5':
            result = 5;
            break;
        case '6':
            result = 6;
            break;
        case '7':
            result = 7;
            break;
        case '8':
            result = 8;
            break;
        case '9':
            result = 9;
            break;
        }
        return result;
    }

    public StringBuffer toStringBuffer() {
        StringBuffer result = new StringBuffer("");
        for (int i = 0; i < Numbers.length; i++) {
            result.insert(0, Numbers[i]);
        }
        if (!PlusMinus)
            result.insert(0, '-');
        return result;
    }

    // 四则运算：
    public BigINT addition(BigINT b) {
        BigINT result = new BigINT(new StringBuffer("0"), true);
        int[] addition1 = Numbers;
        int[] addition2 = b.Numbers();
        int carry = 0;
        if (this.PlusMinus == b.PlusMinus) {
            StringBuffer r = new StringBuffer("");
            if (addition1.length >= addition2.length) {
                for (int i = 0; i < addition2.length; i++) {
                    int n = addition1[i] + addition2[i] + carry;
                    carry = 0;
                    if (n >= 10) {
                        n = n - 10;
                        carry++;
                    }
                    r.insert(0, n);
                }
                for (int i = addition2.length; i < addition1.length; i++) {
                    int n = addition1[i] + carry;
                    carry = 0;
                    if (n >= 10) {
                        n = n - 10;
                        carry++;
                    }
                    r.insert(0, n);
                }
                if (carry != 0)
                    r.insert(0, carry);
                result = new BigINT(r, this.PlusMinus);
            } else {
                r = (b.addition(this)).toStringBuffer();
                result = new BigINT(r, this.PlusMinus);
            }
        } else {
            if (this.PlusMinus)
                result = this.subtration(b.Minus());
            else
                result = b.subtration(this.Minus());
        }
        return result;
    }

    public BigINT subtration(BigINT b) {
        BigINT result = new BigINT(new StringBuffer("0"), true);
        int[] subtration1 = Numbers;
        int[] subtration2 = b.Numbers();
        int carry = 0;
        if (this.PlusMinus == b.PlusMinus) {
            StringBuffer r = new StringBuffer("");
            if (isEquals(subtration1, subtration2) == 1) {
                for (int i = 0; i < subtration2.length; i++) {
                    int n = subtration1[i] - subtration2[i] - carry;
                    carry = 0;
                    if (n < 0) {
                        n = n + 10;
                        carry++;
                    }
                    r.insert(0, n);
                }
                for (int i = subtration2.length; i < subtration1.length; i++) {
                    int n = subtration1[i] - carry;
                    carry = 0;
                    if (n < 0) {
                        n = n + 10;
                        carry++;
                    }
                    r.insert(0, n);
                }
                while (r.charAt(0) == '0') {
                    r.delete(0, 0 + 1);
                }// 删除多余的零
                result = new BigINT(r, this.PlusMinus);
            }
            if (isEquals(subtration1, subtration2) == -1) {
                result = b.subtration(this).Minus();
            }
        } else {
            if (this.PlusMinus)
                result = this.addition(new BigINT(subtration2, true));
            if (b.PlusMinus)
                result = ((new BigINT(subtration1, true)).addition(b)).Minus();
        }
        return result;
    }

    public BigINT multiplication(BigINT b) {
        BigINT result = new BigINT(new StringBuffer("0"), true);
        int[] multiplication1 = Numbers;
        int[] multiplication2 = b.Numbers();
        BigINT[] Lines = new BigINT[multiplication2.length];
        for (int i = 0; i < multiplication2.length; i++) {
            int carry = 0;
            int n = 0;
            int aLine[] = new int[multiplication1.length + i + 1];
            for (int j = 0; j < multiplication1.length; j++) {
                n = multiplication1[j] * multiplication2[i] + carry;
                carry = 0;
                if (n >= 10) {
                    carry = n / 10;
                    n = n % 10;
                }
                aLine[i + j] = n;
            }
            if (carry != 0)
                aLine[i + multiplication1.length] = carry;
            for (int j = 0; j < i; j++)
                aLine[j] = 0;
            if (aLine[aLine.length - 1] == 0) {
                int[] help = new int[aLine.length - 1];
                for (int j = 0; j < help.length; j++) {
                    help[j] = aLine[j];
                }
                aLine = help;
            }
            Lines[i] = new BigINT(aLine, true);
        }
        for (int i = 0; i < Lines.length; i++) {
            result = result.addition(Lines[i]);
        }
        if (this.PlusMinus != b.PlusMinus)
            result.Minus();
        return result;
    }

    public BigINT division(BigINT b) {
        BigINT result = new BigINT(new StringBuffer("0"), true);
        int[] division1 = Numbers;
        int[] division2 = b.Numbers();
        if (isEquals(division1, division2) == 0)
            result = new BigINT(new StringBuffer("1"),
                    (this.PlusMinus == b.PlusMinus));
        if (isEquals(division1, division2) == -1)
            result = new BigINT(new StringBuffer("0"), true);
        if (isEquals(division1, division2) == 1) {
            int c = division1.length - division2.length;
            BigINT help = new BigINT(new StringBuffer("0"), true);
            BigINT n = new BigINT(new StringBuffer("0"), true);// 计数器
            if (c != 0) {
                while (c >= 0) {
                    BigINT nn = new BigINT(new StringBuffer("1"), true);// 计数器的步长值
                    BigINT helphelp = new BigINT(b.Numbers, true);// 大数的步长值
                    for (int i = 0; i < c; i++) {
                        helphelp = helphelp.multiplication(new BigINT(
                                new StringBuffer("10"), true));
                        nn = nn.multiplication(new BigINT(
                                new StringBuffer("10"), true));
                    }
                    while (isEquals(this.Numbers, help.Numbers) == 1) {
                        help = help.addition(helphelp);
                        n = n.addition(nn);
                    }
                    c--;
                    nn = new BigINT(new StringBuffer("1"), true);// 计数器的步长值
                    helphelp = new BigINT(b.Numbers, b.PlusMinus);// 大数的步长值
                    if (c != 0) {
                        for (int i = 0; i < c; i++) {
                            helphelp = helphelp.multiplication(new BigINT(
                                    new StringBuffer("10"), true));
                            nn = nn.multiplication(new BigINT(new StringBuffer(
                                    "10"), true));
                        }
                        while (isEquals(this.Numbers, help.Numbers) == -1) {
                            help = help.subtration(helphelp);
                            n = n.subtration(nn);
                        }
                        c--;
                    }
                }
            } else {
                help = new BigINT(new StringBuffer("0"), true);
                while (isEquals(this.Numbers, help.Numbers) == 1) {
                    help = help.addition(b);
                    n = n.addition(new BigINT(new StringBuffer("1"), true));
                }
            }
            if (this.Numbers.length == 1
                    && (this.Numbers[0] == 3 || this.Numbers[0] == 5
                            || this.Numbers[0] == 7 || this.Numbers[0] == 9)) {
                n = n.subtration(new BigINT(new StringBuffer("1"), true));
            }
            result = n;
        }
        if (this.PlusMinus != b.PlusMinus)
            result.Minus();
        return result;
    }

    public BigINT power(BigINT b) {
        BigINT result = new BigINT(new StringBuffer("1"), true);
        /*
         * BigINT n = b; if (b.PlusMinus) { while (!(n.Numbers.length == 1 &&
         * n.Numbers[0] == 0)) { result = result.multiplication(this); n =
         * n.subtration(new BigINT(new StringBuffer("1"), true)); } }
         */
        result = powerhelp(this, b);
        return result;
    }

    public int isEquals(int a[], int b[]) {
        int result = 0;
        if (a.length > b.length)
            result = 1;
        if (a.length < b.length)
            result = -1;
        if (a.length == b.length) {
            for (int i = 1; i <= a.length; i++) {
                if (a[a.length - i] > b[b.length - i]) {
                    result = 1;
                    break;
                }
                if (a[a.length - i] < b[b.length - i]) {
                    result = -1;
                    break;
                }
            }
        }
        return result;
    }

    public int[] addZero(int[] Numbers, int n) {
        int[] result = new int[Numbers.length + n];
        for (int i = 0; i < n; i++) {
            result[i] = 0;
        }
        for (int i = n; i < result.length; i++) {
            result[i] = Numbers[i - n];
        }
        return result;
    }

    public BigINT powerhelp(BigINT a, BigINT b) {
        BigINT result;
        int[] n1 = { 1 };
        int[] n2 = { 2 };
        BigINT nof1 = new BigINT(n1, true);
        BigINT nof2 = new BigINT(n2, true);
        BigINT dividBigINT = b.division(nof2);
        BigINT help = a;
        if (isEquals(b.Numbers, nof1.Numbers) == 1) {
            help = powerhelp(a, dividBigINT);
            help = help.multiplication(help);
        }
        int last = b.Numbers[0];
        if (last == 3 || last == 5 || last == 7 || last == 9) {
            help = help.multiplication(a);
        }
        return help;
    }
}