如何比较大字符串整数值

Question

目前我正在开发一个处理非常大的integer数字的程序。

为了防止命中 intiger.maxvalue 一个将字符串处理为数字的脚本，并将它们拆分为 List<int> 如下

0 是当前已知的最高值

列表条目 0：123（0.23 亿）
列表条目 1：321（三十二万一千）
列表条目 2：777（七百七十七）

现在我的问题是：如何检查传入的字符串值是否可以从这些值中减去？

我目前做的减法的开始是这样的，但是我卡在了减法部分

public bool Subtract(string value)
{
    string cleanedNumeric = NumericAndSpaces(value);
    List<string> input = new List<string>(cleanedNumeric.Split(' '));

    // In case 1) the amount is bigger 2) biggest value exceeded by a 10 fold 
    // 3)  biggest value exceeds the value
    if (input.Count > values.Count ||
        input[input.Count - 1].Length > values[0].ToString().Length ||
        FastParseInt(input[input.Count -1]) > values[0])
        return false;

    // Flip the array for ease of comparison
    input.Reverse();

    return true;
}

编辑此程序中可实现的最高数量的当前目标是 Googolplex 并且仅限于 .net3.5 MONO

Answer 1

你应该对此做一些测试，因为我没有运行广泛的测试，但它对我已经完成的案例有效。此外，可能值得确保字符串中的每个字符都是真正有效的整数，因为此过程会在给定非整数字符的情况下爆炸。最后，它期望减数和被减数都为正数。

    static void Main(string[] args)
    {
        // In subtraction, a subtrahend is subtracted from a minuend to find a difference.
        string minuend = "900000";
        string subtrahend = "900001";

        var isSubtractable = IsSubtractable(subtrahend, minuend);
    }

    public static bool IsSubtractable(string subtrahend, string minuend)
    {
        minuend = minuend.Trim();
        subtrahend = subtrahend.Trim();

        // maybe loop through characters and ensure all are valid integers

        // check if the original number is longer - clearly subtractable
        if (minuend.Length > subtrahend.Length) return true;
        // check if original number is shorter - not subtractable
        if (minuend.Length < subtrahend.Length) return false;

        // at this point we know the strings are the same length, so we'll
        // loop through the characters, one by one, from the start, to determine
        // if the minued has a higher value character in a column of the number.
        int numberIndex = 0;

        while (numberIndex < minuend.Length )
        {
            Int16 minuendCharValue = Convert.ToInt16(minuend[numberIndex]);
            Int16 subtrahendCharValue = Convert.ToInt16(subtrahend[numberIndex]);

            if (minuendCharValue > subtrahendCharValue) return true;
            if (minuendCharValue < subtrahendCharValue) return false;

            numberIndex++;
        }

        // number are the same
        return true;
    }

Answer 2

[BigInteger](https://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx) 的大小是任意的。

运行不信看这段代码

        var foo = new BigInteger(2);


        while (true)
        {
            foo = foo * foo;
        }

事情变得疯狂。我的调试器 (VS2013) 在完成之前无法表示数字。运行它用了很短的时间，从 ToString 中得到了一个以 10 为基数的 120 万位数字。它足够大。对象有 2GB 的限制，在 .NET 4.5 中可以通过设置 gcAllowVeryLargeObjects

来覆盖

如果您使用的是 .NET 3.5，现在该怎么办？您基本上需要重新实现 BigInteger（显然只需要您需要的，里面有很多东西）。

public class MyBigInteger
{
     uint[] _bits; // you need somewhere to store the value to an arbitrary length.

.....

您还需要对这些数组进行数学运算。这是 BigInteger 的 Equals 方法：

 public bool Equals(BigInteger other)
    {
        AssertValid();
        other.AssertValid();

        if (_sign != other._sign)
            return false;
        if (_bits == other._bits) 
            // _sign == other._sign && _bits == null && other._bits == null
            return true;

        if (_bits == null || other._bits == null)
            return false;
        int cu = Length(_bits);
        if (cu != Length(other._bits))
            return false;
        int cuDiff = GetDiffLength(_bits, other._bits, cu);
        return cuDiff == 0;
    }

它基本上对字节数组进行廉价的长度和符号比较，然后，如果没有产生差异，请交给 GetDiffLength。

    internal static int GetDiffLength(uint[] rgu1, uint[] rgu2, int cu)
    {
        for (int iv = cu; --iv >= 0; )
        {
            if (rgu1[iv] != rgu2[iv])
                return iv + 1;
        }
        return 0;
    }

哪个执行循环遍历数组以查找差异的昂贵检查。

你所有的数学都必须遵循这种模式，并且在很大程度上可以从 .Net source code.

中删除

Googleplex 和 2GB：

这里 2GB 的限制成为一个问题，因为您将需要 3.867×10^90 gigabyte 的对象大小。这就是您放弃或变得聪明并将对象存储为力量的时刻，但代价是无法代表很多对象。 *2

如果您降低预期，它实际上不会改变 BigInteger 的数学运算以将 _bits 拆分为多个锯齿状数组 *1。你稍微改变一下廉价支票。您不是检查数组的大小，而是检查子数组的数量，然后是最后一个的大小。然后循环需要更复杂一点（但不多），因为它对每个子数组进行元素数组比较。还有其他更改，但这绝不是不可能的，并且可以让您摆脱 2GB 的限制。

*1 注意使用交错数组[][]，而不是多维数组[]，它们仍然受到相同的限制。

*2 即放弃精度，存储尾数和指数。如果你看看浮点数是如何实现的，它们不能代表它们的最大值和最小值之间的所有数字（因为运行ge 中的实数是 'bigger' 而不是无限）。他们在精度和运行ge 之间进行了复杂的权衡。如果您想这样做，查看 float 实现将比采用像 Biginteger 这样的整数表示更有用。

如何比较大字符串整数值

How to compare large string integer values

c#

string

int