论坛 › C\C++交流 › 大整数的存储与高精度运算

798236606 发表于 2020-2-1 10:02:19

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

本帖最后由 798236606 于 2020-2-1 11:33 编辑

#include<cstdio>
#include<cstring>

typedef struct BIGN{                                         //定义大整数类型
    int num;                                        //从低位到高位存储大整数
    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 == '-')
    {
      a.is_neg = true;
      a.len--;
      s++;
    }
   
    for (int i = 0; i < a.len; i++)
      a.num = s - '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);
}

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 > b.num)
            return 1;
      
      if (a.num < b.num)
            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 + b.num + carry;
      
      c.num = temp % 10;
      carry = temp / 10;
    }
   
    if (carry)
      c.num = 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 < b.num)
      {
            a.num--;
            a.num += 10;
      }
      
      c.num = a.num - b.num;
    }
   
    while (c.len > 1 && !c.num)
      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 * b + carry;
      
      c.num = temp % 10;
      carry = temp / 10;
    }

    while (carry)
    {
      c.num = 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;
      c.num = r / b;
      r = r % b;
    }
   
    while (c.len > 1 && !c.num)
      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 = "-123";
    char s2 = "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

查看完整版本: 大整数的存储与高精度运算