大整数的存储与高精度运算

798236606

#include<cstdio>
#include<cstring>

typedef struct BIGN{                                         //定义大整数类型
    int num[1000];                                        //从低位到高位存储大整数
    int len;
    bool is_neg;
    
    BIGN()                                                        //初始化构造函数                                        
    {
        memset(num, 0, sizeof(num));
        len = 0;
        is_neg = false;
    };
}bign;

bign str2bign(char *s)                                        //字符串转大整数
{
    bign a;
    
    a.len = strlen(s);
    
    if (s[0] == '-')
    {
        a.is_neg = true;
        a.len--;
        s++;
    }
    
    for (int i = 0; i < a.len; i++)
        a.num[i] = s[a.len - 1 - i] - '0';
        
    return a;
}

void print_bign(bign a)                                //打印大整数
{
    if (a.is_neg)
        putchar('-');
        
    for (int i = a.len - 1; i >= 0; i--)
        printf("%d", a.num[i]);
}

int u_campare(bign a, bign b)                        //无符号比较大小,a > b则返回1，a < b返回-1，a == b返回0
{    
    if (a.len > b.len)
        return 1;
        
    if (a.len < b.len)
        return -1;
        
    for (int i = a.len - 1; i >= 0; i--)
    {
        if (a.num[i] > b.num[i])
            return 1;
        
        if (a.num[i] < b.num[i])
            return -1;
    }
    
    return 0;
}

int campare(bign a, bign b)                                //有符号比较大小
{

    if (a.is_neg == b.is_neg)
        return a.is_neg ? -u_campare(a, b) : u_campare(a, b);
    else
        return a.is_neg ? -1 : 1;
}

bign u_add(bign a, bign b)                                //无符号加
{
    bign c;
    int carry = 0;
    
    for (int i = 0; i < a.len || i < b.len; i++)
    {
        int temp = a.num[i] + b.num[i] + carry;
        
        c.num[c.len++] = temp % 10;
        carry = temp / 10;
    }
    
    if (carry)
        c.num[c.len++] = carry;

    return c;
}

bign u_sub(bign a, bign b)                                //无符号减
{
    bign c;
    
    if (u_campare(a, b) < 0)
    {
        bign temp = a;
        
        a = b;
        b = temp;
        c.is_neg = true;
    }
    
    for (int i = 0; i < a.len || i < b.len; i++)
    {
        if (a.num[i] < b.num[i])
        {
            a.num[i + 1]--;
            a.num[i] += 10;
        }
        
        c.num[c.len++] = a.num[i] - b.num[i];
    }
    
    while (c.len > 1 && !c.num[c.len - 1])
        c.len--;

    return c;
}

bign muti(bign a, int b)                                //有符号乘（大整数乘整形）
{
    bign c;
    int carry = 0;
    
    if (!b)
    {
        c.len++;
        c.is_neg = a.is_neg;
        
        return c;
    }
    
    if (a.is_neg + (b < 0) == 1)
        c.is_neg = true;
        
    if (b < 0)
        b = -b;
        
    for (int i = 0; i < a.len; i++)
    {
        int temp = a.num[i] * b + carry;
        
        c.num[c.len++] = temp % 10;
        carry = temp / 10;
    }

    while (carry)
    {
        c.num[c.len++] = carry % 10;
        carry /= 10;
    }    

    return c;
}

bign divi(bign a, int b)                                        //有符号除（大整数除整形）
{
    bign c;
    int r = 0;
    
    if (!b)
    {
        puts("0 can not be divisor!!");
        
        return c;
    }
    
    if (a.is_neg + (b < 0) == 1)
        c.is_neg = true;
        
    if (b < 0)
        b = -b;
    
    c.len = a.len;    
    for (int i = a.len - 1; i >= 0; i--)
    {
        r = r * 10 + a.num[i];
        c.num[i] = r / b;
        r = r % b;
    }
    
    while (c.len > 1 && !c.num[c.len - 1])
        c.len--;

    return c;
}

bign add(bign a, bign b)                                //有符号加
{
    bign c;
    
    if (a.is_neg == b.is_neg)
    {
        c = u_add(a, b);
        
        if (a.is_neg)
            c.is_neg = true;        
    }
    else
        c = a.is_neg ? u_sub(b, a) : u_sub(a, b);

    return c;
}

bign sub(bign a, bign b)                                //有符号减
{
    bign c;
    
    if (a.is_neg != b.is_neg)
    {
        c = u_add(a, b);
        
        if (a.is_neg)
            c.is_neg = true;        
    }
    else
        c = a.is_neg ? u_sub(b, a) : u_sub(a, b);

    return c;
}

int main(void)
{
    char s1[100] = "-123";
    char s2[100] = "23";
    bign a = str2bign(s1), b = str2bign(s2);
    
    print_bign(divi(a, 12));
    
    return 0;
}

相关题目：

PTA B_1017 A除以B
https://fishc.com.cn/thread-154914-1-1.html

PTA A_1023 Have Fun with Numbers
https://fishc.com.cn/thread-154917-1-1.html

PTA A_1024 Palindromic Number
https://fishc.com.cn/thread-154921-1-1.html