BigInteger 家庭作业需要帮助

Question

有人告诉我必须编写一个 BigInteger 类，我知道有一个类，但我必须编写自己的类。我将采用整数或字符串并将它们转换为数组来存储它们。从那里我将允许对数字进行加法、减法和乘法。我让它获取整数和字符串并制作数组，效果很好。我对其余的有问题。

对于添加，我尝试制作一些东西来检查数字类型数组的大小，然后设置较小和较大的值。从那里开始，我让它循环，直到它到达较小的末尾，并且当它循环时，它将数组的该部分的数字作为两个数字并将它们相加。现在这是可以的，直到它们大于 10，在这种情况下我需要结转一个数字。我想我在某个时候也有这样的工作。

请记住，我的 BigInt 有两件事：数字数组和符号整数（1 或 -1）。

因此，在这种情况下，我在添加正确且符号正确时遇到问题。与减法相同。

至于乘法，我完全迷失了，甚至没有尝试过。下面是我尝试制作的一些代码：（添加函数），请帮助我。

public BigInt add(BigInt val){

        int[] bigger;
        int[] smaller;
        int[] dStore;
        int carryOver = 0;
        int tempSign = 1;

        if(val.getSize() >= this.getSize()){
            bigger = val.getData();
            smaller = this.getData();

            dStore = new int[val.getSize()+2];

            if(val.getSign() == 1){
                tempSign = 1;
            }else{
                tempSign = -1;
            }

        }else{

            bigger = this.getData();
            smaller = val.getData();

            dStore = new int[this.getSize()+2];

            if(this.getSign() == 1){
                tempSign = 1;
            }else{
                tempSign = -1;
            }
        }


        for(int i=0;i<smaller.length;i++){
            if((bigger[i] < 0 && smaller[i] < 0) || (bigger[i] >= 0 && smaller[i] >= 0)){
                dStore[i] = Math.abs(bigger[i]) + Math.abs(smaller[i]) + carryOver;
            }else if((bigger[i] <= 0 || smaller[i] <= 0) && (bigger[i] > 0 || smaller[i] > 0)){
                dStore[i] = bigger[i] + smaller[i];
                dStore[i] = Math.abs(dStore[i]);
            }
            if(dStore[i] >= 10){
                dStore[i] = dStore[i] - 10;
                if(i == smaller.length - 1){
                    dStore[i+1] = 1;
                }
                carryOver = 1;
            }else{
                carryOver = 0;
            }
        }

        for(int i = smaller.length;i<bigger.length;i++){
            dStore[i] = bigger[i];
        }

        BigInt rVal = new BigInt(dStore);
        rVal.setSign(tempSign);

        return rVal;

Answer 1

如果您知道如何添加和手动相乘大数，在 Java 中实现这些算法并不困难。

Answer 2

如果它们的符号不同，您需要实际减去数字（如果合适的话还可以借用）。另外，您的进位函数似乎无法超出较小数字的长度（所进位的“1”被覆盖）。

为了进一步了解符号，您有几种不同的情况（假设这些情况下这是正数，而 val 是负数）：

1. 如果它有更多数字，那么您需要从中减去 val，结果将为正数
2. 如果 val 有更多的位数，那么你需要从 val 中减去它，结果将为负
3. 如果它们有相同的位数，你必须扫描找出哪个更大（从最高有效位开始）。

当然，如果两者都是正数，那么您只需按正常方式相加，如果两者都是负数，则相加，然后将结果设置为负数。

Answer 3

现在我们知道数字是反向存储的......
我认为如果数字具有相同的符号，您的代码就可以工作。我尝试了以下测试用例：

• 相同的长度，非常基本的测试。
• 长度相同，中间有残留。
• 长度相同，最后结转。
• 长度相同，中间和末端结转
• 第一个数字较长，中间和末端结转
• 第二个数字较长，中间和末端结转
• 均为负数，第一个数字较长，中间和末端结转最后

一切都很顺利。
但是，当一个为正，一个为负时，就不能正常工作了。
这并不奇怪，因为 -1 + 7 实际上更像是减法而不是加法。您应该将其视为 7-1，如果您检查这种情况并调用减法，对您来说会容易得多。
同样，-1 - 1 应被视为加法，即使它看起来像减法。

Answer 4

实际上，几年前我已经用汇编编写了一个大数字库；如果有帮助的话，我可以在这里添加乘法代码。我给您的建议是不要尝试自己编写函数。已经有一些已知的方法可以对大数进行加、减、乘、除、powmod、xgcd 等运算。我记得我正在阅读 Bruce Schneier 的《应用密码学》一书和 Randall Hyde 的《装配艺术》。两者都有所需的算法来做到这一点（也在伪代码中）。我强烈建议您看一下，尤其是第二个，因为它是在线免费资源。