比较大整数 [英] Comparing big integers

问题描述

我有一个bigint类，它使用一个名为SafeArray的数组，我在另一个类中创建。我无法使用矢量。 set和get函数调用来自SafeArray类。获取数组位置的int参数，并设置2个int参数（一个用于位置，一个用于值）。这个bigint类中的所有方法都可以正常工作（我们不必考虑负整数），除了我的compare方法需要工作。我希望它能够比较两个bigint，如果（const bigint和& A）数字大于另一个（cout 1），如果它更小（cout 2），如果它们是相同的（cout 0）。任何有关此方法的帮助将不胜感激。谢谢

I've got a bigint class that uses an array called SafeArray that I created in a different class. I couldn't use vectors. The set and get function calls are from the SafeArray class. Get takes an int parameter for array position and set takes 2 int parameters (one for position and one for value). All methods in this bigint class work fine (we don't have to account for negative integers) except my compare method needs work. I want it to be able to compare two bigints and if the (const bigint and &A) number is larger than the other (cout 1) if it is smaller (cout 2) if they are the same (cout 0). Any help with this method would be greatly appreciated. Thanks

int size = 35; //will get bigger, small now just for testing
class bigint
{
    SafeArray<int> *arr;
public:
    bigint()            //initializes to zero
    {
        arr = new SafeArray<int>;
        for(int i =0;i < size; i++)
            arr->set(i,0);
    }

    void print()                 //prints numbers without zeroes in front
    {
        bool start_num=false;
        for(int i = 0;i <arr->get_size() ;i++)
        {
            if(arr->get(i)!=0 && start_num==false )
            {start_num=true;
                cout << arr->get(i);}
         else if(start_num==true)
             cout<<arr->get(i);                
        }

       cout<<endl;
    }

    void assign(const bigint &A)                  //
    {
        for(int i=0;i<arr->get_size();i++)
        {                                   //Ways to initialize stuff
            arr->set(i,A.arr->get(i));
        }        
    }

    void assign(int num)     
{
        for(int i = arr-&gt;get_size()- 1; i &gt;= 0; i--)
        {
            arr-&gt;set(i,num%10);
            num /=10;
        }
    }

    void assign(string num)                        //
    {
        long len = num.length();
        int j=arr-&gt;get_size()-1;
        for(long i=len-1;i&gt;=0;i--)
        {
            arr-&gt;set(j,num[i]-48);
            j--;
        }
    }

    void add(const bigint &amp;A)                    //add big ints
    {
        int carry=0;
        for(int i=size-1;i&gt;=0;i--)
           {
               int result = arr-&gt;get(i)+A.arr-&gt;get(i)+carry;
               arr-&gt;set(i,result%10);
               carry=result/10;
           }
    }

    void subtract(const bigint &amp;A)                 //subtract big ints
    {
        int borrow = 0;
        for(int i=size-1; i &gt;= 0; --i)
        {
            int result=((arr-&gt;get(i) - A.arr-&gt;get(i) - borrow));
            if(result &lt; 0)
            {
                arr-&gt;set(i, result + 10);
                borrow = 1;
            }
            else
            {
                arr-&gt;set(i, result);
                borrow = 0;
            }
        }
    }

//int compare(const bigint &amp;A)               //compare big ints
//    {
//
//        for(int i&lt;size;i&gt;0;i--)
//            {
//                if(A.arr-&gt;get(i) &gt; arr-&gt;get(i))
//                    {
//                    return 1;
//                    }
//                else if(A.arr-&gt;get(i) &lt; arr-&gt;get(i))
//                    {
//                        return -1;
//                    }
//                else
//                    {
//                        return 0;
//                    }
//            }
//
//    }

};
int main()
{
    bigint a, b, c;

    a.assign(&quot;12345678&quot;);                             //for testing
    b.assign(&quot;12345678&quot;);
    //a.compare(b);
    a.print();
    c.assign(24691357);        // 696969 is small enough to be an int.
    a.add(b);                // a += b;
    a.subtract(c);           // a -= b;
    a.print();

    return 0;
}</pre>

推荐答案

您的第一个错误是使用 int 作为基类型，是数组元素类型。您应该使用无符号类型，即使您想要开发有符号的大型int类型，否则您将丢失元素类型的值范围的一半。这对于比较尤其重要。



看看如何比较纸上的两个大整数。例如，您有十位数的十进制数字。您对齐记录的数字以比较表示相同度数为10的数字。然后您开始与最高有效数字进行比较。只有当最高有效数字相同时，才会逐个移动到最低有效数字。



您对阵列执行相同操作。你从最重要的结束开始。如果你正确地做了其他一切，那么你的数组元素代表一个数字，其中包含2 ³² 或2 ⁶⁴ 值。如果两个数组元素不相等，则与最重要的结束和停止比较进行比较。然后你需要比较其他数组元素。

-SA

Your first mistake is using int as a base type, an array element type. You should use unsigned type, even if you wanted to develop signed big int type, otherwise you are loosing half of value range of the element type. This is especially important for comparison.

Look how you compare two big integers on paper. You have, say, decimal digits with 10 values. You align the recorded numbers to compare the digits representing the same degree of 10. Then you start comparison with the most significant digit. Only if the most significant digit is the same, you move to the least significant digit, one by one.

You do the same with your arrays. You start with most significant end. If you do everything else correctly, your array element represents, say, one digit with 2³² or 2⁶⁴ values. You compare with most significant end and stop comparison if two array element are not equal. Then you need to compare other array elements.

—SA

比较中的错误功能很明显。我只能重复以前所有问题中给出的建议：使用调试器或用铅笔和纸张逐步执行代码。当两个数字的高位数相同时，您将在for循环的第一次迭代中检测到问题。

The error in your compare function is obvious. I just can only repeat the advice given to you in all of previous questions: Use a debugger or step through the code with pencil and paper. You will detect the problem in the very first iteration of the for loop when the two numbers are identical in their high-order digit.

这篇关于比较大整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！