大數計算——加減乘除取餘

大數計算

核心代碼：

#include <iostream>
#include <cstring>//包含memset函數，友善初始化
#include <string>

using namespace std;

const int MAXN = 10000;

struct BigInteger
{
    int digit[MAXN];//儲存位數，逆序存儲的
    int length;//儲存長度

    BigInteger();//初始化函數
    BigInteger(int x);//int型數轉化
    BigInteger(string s);//string轉化

    BigInteger operator= (const BigInteger& b);//重載指派号

    bool operator<= (const BigInteger& b);//重載比較符号
    bool operator== (const BigInteger& b);

    BigInteger operator+ (const BigInteger& b);//重載運算符
    BigInteger operator- (const BigInteger& b);
    BigInteger operator* (const BigInteger& b);
    BigInteger operator/ (const BigInteger& b);
    BigInteger operator% (const BigInteger& b);
};

BigInteger :: BigInteger()
{
    memset(digit,0,sizeof(digit));//位數初始化為0
    length = 0;//長度置0
}

BigInteger :: BigInteger(int x)
{
    memset(digit,0,sizeof(digit));//位數初始化為0
    length = 0;//長度置0

    if(x == 0)
    {
        digit[length ++] = x;
    }
    while(x != 0)//逆序存儲
    {
        digit[length ++] = x%10;
        x /= 10;
    }
}

BigInteger :: BigInteger(string s)
{
    memset(digit,0,sizeof(digit));//初始化,這樣即使字元串為空串也不會出現問題
    length = s.size();

    for(int i=0; i<length; i++)
    {
        digit[i] = s[length-1-i]-'0';//逆序存儲
    }
}

BigInteger BigInteger ::operator= (const BigInteger& b)
{
    memset(digit,0,sizeof(digit));//位數初始化為0
    length = b.length;

    for(int i=0; i<length; i++)
    {
        digit[i] = b.digit[i];
    }

    return *this;//這個傳回值很重要
}

bool BigInteger ::operator<=(const BigInteger& b)
{
    if(length < b.length)
    {
        return true;
    }
    else if(length > b.length)
    {
        return false;
    }
    else//位數相同時要單獨判斷
    {
        for(int i=length-1; i>=0; i--)
        {
            if(digit[i] == b.digit[i])
            {
                continue;
            }
            else
            {
                return digit[i] < b.digit[i];//使代碼更簡潔
            }
        }
        return true;//完全相等的情況
    }
    return true;
}

bool BigInteger ::operator==(const BigInteger& b)
{
    if(length != b.length)
    {
        return false;
    }
    else
    {
         for(int i=length-1; i>=0; i--)
        {
            if(digit[i] != b.digit[i])
            {
                return false;
            }
        }
    }
    return true;
}

BigInteger BigInteger ::operator+(const BigInteger& b)//逆序存儲的，digit[0]為最低位
{
    BigInteger answer;

    int carry = 0;//進位
    for(int i=0; i<length || i<b.length; i++)//由于digit初值賦的全為0，是以可以一直加到長度的最大值，不會影響結果
    {
        int current = carry+digit[i]+b.digit[i];//計算目前位
        answer.digit[answer.length ++] = current%10;//目前位指派
        carry = current/10;//産生進位
    }

    if(carry != 0)//最高位也産生進位
    {
        answer.digit[answer.length ++] = carry;
    }

    return answer;
}

BigInteger BigInteger ::operator-(const BigInteger& b)
{
    BigInteger answer;

    int carry = 0;//特殊的“進位”，若目前位不夠，則向下一位借1，令carry=-1即可
    for(int i=0; i<length; i++)//必須確定為大數減小數
    {
        int current = digit[i]-b.digit[i]-carry;//計算目前位

        if(current < 0)//不夠則向下一位借1
        {
            current += 10;
            carry = 1;
        }
        else//夠了則令借位為0
        {
            carry = 0;
        }

        answer.digit[answer.length ++] = current;//存儲目前位結果
    }

    while(answer.digit[answer.length-1] == 0 && answer.length > 1)//消除前導0
    {
        answer.length --;
    }

    return answer;
}

BigInteger BigInteger ::operator*(const BigInteger& b)
{
    BigInteger answer;
    answer.length = length+b.length;//最大位數

    for(int i=0; i<length; i++)
    {
        for(int j=0; j<b.length; j++)
        {
            answer.digit[i+j] += digit[i]*b.digit[j];//先計算乘積，不進位
        }
    }

    for(int i=0; i<answer.length; i++)//統一處理進位問題
    {
        answer.digit[i+1] += answer.digit[i]/10;
        answer.digit[i] %= 10;
    }

    while(answer.digit[answer.length-1] == 0 && answer.length > 1)//消除前導0
    {
        answer.length --;
    }

    return answer;
}

BigInteger BigInteger ::operator/(const BigInteger& b)
{
    BigInteger answer;
    answer.length = length;//商的最大位數
    BigInteger remainder = BigInteger(0);//暫存的計算數，最終為餘數，初始化為0
    BigInteger temp = b;//記得要重載'='号

    for(int i = length-1; i >= 0; i--)//除法是從最高位開始做減法的，循環完成後，需要餘數則傳回remainder，需要商則傳回answer
    {
        if(! (remainder.digit[0] == 0 && remainder.length == 1))//計算數不為0時，即待計算數有數值時
        {
            for(int j = remainder.length-1; j>=0; j--)//計算數右移一位
            {
                remainder.digit[j+1] = remainder.digit[j];
            }
            remainder.length ++;//長度加1
        }

        remainder.digit[0] = digit[i];//計算數最低位補上被除數的目前位

        while(temp <= remainder)//目前待計算數不比被除數小的時候，做減法；重載'<='号
        {
            remainder = remainder-temp;//重載'-'号
            answer.digit[i] ++;//目前商的位置上加1
        }
    }

    while(answer.digit[answer.length-1] == 0 && answer.length > 1)//消除前導0
    {
        answer.length --;
    }

    return answer;
}

BigInteger BigInteger ::operator%(const BigInteger& b)//和除法的思路類似，隻不過不傳回商，傳回餘數
{
    BigInteger remainder = BigInteger(0);//待運算數，初始化為0
    BigInteger temp = b;//存儲被除數

    for(int i=length-1; i>=0; i--)
    {
        if(! (remainder.digit[0] == 0 && remainder.length == 1))//待運算數不為0時
        {
            for(int j=remainder.length-1; j>=0; j--)//右移一位
            {
                remainder.digit[j+1] = remainder.digit[j];
            }
            remainder.length ++;
        }

        remainder.digit[0] = digit[i];//最低位補上運算數

        while(temp <= remainder)//目前位上重複做減法
        {
            remainder = remainder-temp;
        }
    }
    return remainder;
}

           

簡單驗證一下

void output(const BigInteger& x)//單獨寫個輸出函數，逆序輸出
{
    for(int i=x.length-1; i>=0; i--)
    {
        cout << x.digit[i];
    }
    cout << endl;
}

int main()
{
    string s1,s2;
    while(cin >> s1 >> s2)
    {
        BigInteger x = BigInteger(s1);
        BigInteger y = BigInteger(s2);

        BigInteger result = x+y;
        cout << "+ : ";
        output(result);

        result = x-y;
        cout << "- : ";
        output(result);

        result = x*y;
        cout << "* : ";
        output(result);

        result = x/y;
        cout << "/ : ";
        output(result);

        result = x%y;
        cout << "% : ";
        output(result);
    }
    return 0;
}
           

結果：