如何处理任意大整数

如果您需要大于32位,可以考虑使用64位整数(long-long),或者使用或编写任意精度的数学库,例如。 GNU MP

如果你想滚动你自己的任意精度库,请参阅Knuth的半数值算法,他的代表作第2卷。

事实上,在当今巨大的存储能力下,您可能只需要使用一个字节数组,其中每个字节只包含一个数字(0-9)。然后编写自己的例程,对字节数组进行加法、减法、乘法和除法。

(除法是很难的,但我敢打赌你一定能在某处找到一些代码。)

class BigAssNumber {
    private byte[] value;

    // This constructor can handle numbers where overflows have occurred.
    public BigAssNumber(byte[] value) {
        this.value=normalize(value);
    }

    // Adds two numbers and returns the sum.  Originals not changed.
    public BigAssNumber add(BigAssNumber other) {
        // This needs to be a byte by byte copy in newly allocated space, not pointer copy!
        byte[] dest = value.length > other.length ? value : other.value;         

        // Just add each pair of numbers, like in a pencil and paper addition problem.
        for(int i=0; i<min(value.length, other.value.length); i++)
            dest[i]=value[i]+other.value[i];

        // constructor will fix overflows.
        return new BigAssNumber(dest);
    }

    // Fix things that might have overflowed  0,17,22 will turn into 1,9,2        
    private byte[] normalize(byte [] value) {
        if (most significant digit of value is not zero)
            extend the byte array by a few zero bytes in the front (MSB) position.

        // Simple cheap adjust.  Could lose inner loop easily if It mattered.
        for(int i=0;i<value.length;i++)
            while(value[i] > 9) {
                value[i] -=10;
                value[i+1] +=1;
            }
        }
    }
}

在C++中没有简单的方法来实现它。您必须使用外部库,例如 GNU Multiprecision ,或使用本机支持任意大整数的其他语言,如Python。

其他的海报也提供了图书馆的链接,可以帮你做到这一点,但看起来你正在尝试将其构建到你的语言中。我的第一个想法是:你确定你需要这样做吗?大多数语言都会像其他语言所建议的那样使用附加库。

假设您正在编写一个编译器,并且确实需要此功能,您可以为汇编中任意大的值实现整数算术函数。

例如,一个简单的(但不是最佳的)实现将数字表示为二进制编码的十进制。算术函数可以使用与你用铅笔和纸做数学时相同的算法。

另外,考虑对这些大整数使用专门的数据类型。这样,“正常”整数就可以使用标准的32位算术。

我更喜欢的方法是将我当前的int类型用于32位int(或者在内部将其更改为long long或类似的类型,只要它可以继续使用相同的算法),然后当它溢出时,将其更改为bignum存储,无论是我自己创建的,还是使用外部库。然而,我觉得我需要检查每个算术运算的溢出,大约是算术运算开销的2倍。我怎么解决这个问题?

如果我要实现我自己的语言并且想要支持任意长度的数字,我将使用带有进位/借位概念的目标语言。但是由于没有HLL能够在没有严重性能影响的情况下实现这一点(比如异常),所以我肯定会在汇编中实现它。可能需要一条指令(如x86中的JC)来检查并处理溢出(如x86中的ADC),对于实现任意精度的语言来说,这是可以接受的折衷方案。然后我将使用汇编中编写的一些函数来代替常规运算符,如果您可以利用重载来获得更优雅的输出,甚至更好。但我不认为生成的C++是可维护的(或者意味着要维护)作为目标语言。

或者,只需使用一个比你需要的钟和口哨更多的库,并将其用于所有数字。

作为一种混合方法,检测程序集中的溢出并在溢出时调用库函数,而不是滚动自己的迷你库。