如何比较存储在 int 数组中的大整数？

Question

我正在尝试在 C# 中实现 BigInteger class。现在我被困在一个叫做 isLessThan(HugeInteger b) 的方法上。这是我的class和相应的方法。

class HugeInteger
{
    public int[] array = new int[40];

    public HugeInteger(String s)
    {
        this.input(s);
    } // end constructor

    /*To read a huge integer having upto 40 digits, I am using an integer array to store 
      these values(input is read as a string for this matter) and later on will override 
      ToString() for output if needed.*/
    private void input(String s)
    {
        char[] charInteger = s.ToCharArray();
        int index = 0;
        for (int i = 0; i <= 39 - charInteger.Length; i++)
        {
            array[i] = 0;
        }
        for (int i = 39 - charInteger.Length + 1; i <= 39; i++)
        {

            array[i] = int.Parse(charInteger[index].ToString());
            index++;
        }
    }

    public bool isLessThan(HugeInteger that)
    {

        for (int i = 0; i <= 39; i++)
        {
            if (this.array[i] < that.array[i])
            {
                return true;
            }
        }
        return false;
    }
}

所以基本上，我将 40 位数字存储到每个 HugeInteger 对象的整数数组中。但我确信我的方法 isLessThan(HugeInteger b) 是错误的，而且我忽略了一些简单的事情。那么我应该如何制作正确的 isLessthan(HugeInteger b) 方法呢？

编辑：我的 isLessThan 方法在某些情况下不起作用，比如如果我尝试比较“9873”和“75”，我得到 true，但我需要一个 false。抱歉不清楚。

注意：我将我的输入（如 9873 或 75）作为字符串提供，然后在我的 input 方法中将它们解析为 int，然后将它们存储到整数数组中。

Answer 1

这里是你如何修正你的方法

public bool isLessThan(HugeInteger that)
{
    for (int i = 0; i <= 39; i++)
    {
        if (this.array[i] < that.array[i])
        {
            return true;
        }
        if (this.array[i] > that.array[i])
        {
            return false;
        }
    }
    return false;
}

基本上，当您比较数字时，如果它们不相等，您就会知道一个大于还是小于另一个。只有当它们相等时你才能继续。您目前所拥有的只是检查第一个数字中是否至少有一个对应的数字小于第二个数字。因此，对于 9873 和 75，这是真的，因为 3 < 5。与我的更改一样，只要比较 9 和 0，它就会 return 为假。

Answer 2

好的，让我们来实现比较；典型的方法是使用通用比较（在某些语言中它甚至有一个特殊的运算符 <=>）

  class HugeInteger {
    ...

    // Universal comparator
    //  +1 left > right
    //   0 left == right
    //  -1 left < right
    public static int Compare(HugeInteger left, HugeInteger right) {
      // first, we should deal with null's; let null be the leaset possible value

      // left and right are just the references of one inctance?
      if (Object.ReferenceEquals(left, right)) 
        return 0;
      else if (left == null)
        return -1;
      else if (right == null)
        return 1;

      // Now we checked for null, let's compare both arrays  

      //DONE: no 39, 40 or other magic numbers, but Length 
      for (int i = 0; i < left.array.Length; ++i)
        if (left.array[i] < right.array[i])
          return -1;
        else if (left.array[i] > right.array[i])
          return 1;

      return 0; // no differences found, so left equals to right
    }

实现了比较器就很容易写 isLessThan, isGreaterThan:

    public bool isLessThan(HugeInteger other) {
      return Compare(this, other) < 0;
    }

    public bool isGreaterThan(HugeInteger other) {
      return Compare(this, other) > 0;
    }
    ....

Answer 3

当发生溢出时，CPU 的条件代码被设置为后续指令可能无法提供正确的结果，因此如果您不预测，您所有花哨的逻辑都是徒劳的在它们发生之前溢出。

（你无法检测到溢出：例如，如果我问，

if( MUCHTOOLARGENUMBER > SOMEREASONABLEVALUE ) {

那么我无法保证测试将以何种方式进行评估。）

如何比较存储在 int 数组中的大整数？

How to compare big integers stored in int array?

c#

arrays

biginteger

compareto