Compare very large numbers stored in string

问题:

What is the best way to compare two very large numbers contained in string literals?

For example I want to compare the followings: "90000000000000000000000000000000000000000000000000000000000000000000000000001" "100000000000000000000000000000000000000000000000000000000000000000000000000009"

or

"0000000000111111111111111111111111111111111111111111111111111111111111111111" "0000001111111111111111111111111111111111111111111111111111111111111111111111"

In both cases obviously the second one is greater, but how could I find it out efficiently without iterating on elements?

回答1:

Here is another solution:

    public static int CompareNumbers(string x, string y)
    {
        if (x.Length > y.Length) y = y.PadLeft(x.Length, '0');
        else if (y.Length > x.Length) x = x.PadLeft(y.Length, '0');

        for (int i = 0; i < x.Length; i++)
        {
            if (x[i] < y[i]) return -1;
            if (x[i] > y[i]) return 1;
        }
        return 0;
    }

回答2:

I would personally take the simplest approach: use BigInteger to parse both values, and compare those results. That wouldn't be terribly efficient, but it would be very simple - and then you could benchmark to see whether it's fast enough.

Otherwise, you could find the effective length by ignoring leading zeroes - and if one number is longer than the other, then that's all you need to know. Or write a method to get the "effective" digit of a string which may be shorter, returning 0 if necessary, and then compare from the longer string's length downwards until one string gives a bigger value. Something like:

// Return the digit as a char to avoid bothering to convert digits to their
// numeric values.
private char GetEffectiveDigit(string text, int digitNumber)
{
    int index = text.Length - digitNumber;
    return index < 0 ? '0' : text[index];
}

private int CompareNumbers(string x, string y)
{
    for (int i = int.Max(x.Length, y.Length); i >= 0; i--)
    {
        char xc = GetEffectiveDigit(x, i);
        char yc = GetEffectiveDigit(y, i);
        int comparison = xc.CompareTo(yc);
        if (comparison != 0)
        {
            return comparison;
        }
    }
    return 0;
}

Note that this doesn't check that it's a valid number at all, and it definitely doesn't attempt to handle negative numbers.

回答3:

If by comparison you mean boolean check, this will work:

public class Program
{
    static void Main(string[] args)
    {
        string a = "0000000090000000000000000000000000000000000000000000000000000000000000000000000000001";

        string b = "000100000000000000000000000000000000000000000000000000000000000000000000000000009";

        Console.WriteLine(FirstIsBigger(a, b));

        Console.ReadLine();
    }

    static bool FirstIsBigger(string first, string second)
    {
        first = first.TrimStart('0');
        second = second.TrimStart('0');
        if (first.Length > second.Length)
        {
            return true;
        }
        else if (second.Length == first.Length)
        {
            for (int i = 0; i < first.Length; i++)
            {
                double x = char.GetNumericValue(first[i]);
                double y = char.GetNumericValue(second[i]);
                if (x > y) return true;
                else if (x == y) continue;
                else return false;
            }
        }

        return false;
    }
}