C语言实现大数运算[通俗易懂]

C语言实现大数运算[通俗易懂]由于整型数的位数有限,因此整型数不能满足大整数(超长整数)的运算要求。大整数计算是利用字符串来表示大整数,即用字符串的一位字符表示大整数的一位数值,然后根据四则运算规则实现大整数的四则运算。大数的结构typedefstructbigint{char*num;//指向长整数数组(序号0中保存着最高位)charsign;

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

由于整型数的位数有限,因此整型数不能满足大整数(超长整数)的运算要求 。大整数计算是利用字符串来表示大整数,即用字符串的一位字符表示大整数的一位数值,然后根据四则运算规则实现大整数的四则运算。

大数的结构

typedef struct bigint
{
    char *num;                //指向长整数数组(序号0中保存着最高位) 
    char sign;               //符号(1表示正数,-1表示负数) 
    int digit;                 //保存该数的位数(实际位数) 
}BIGINT, *pBIGINT; 

加法运算

执行加法之前,先判断两数是同号相加还是异号相加,同号则执行加法运算,异号则执行减法运算。在加法运算中,首先将被操作的两个数对齐,然后从低位向高位逐渐相加,在对应位置相加时,要考虑是否有地位相加的进位。

这里写图片描述

实现代码:
首先将被加数中的内容复制到结果数组中,然后从低位逐渐加到结果中去,最后判断加数各位加完之后是否还有进位,如果有则要累加到高位中去。BigintTirm()用于整理大数,去掉前多余的0,并调整其位数

void BigIntAdd(pBIGINT num1,pBIGINT num2,pBIGINT result)
{
    int i,carry;
    carry=0;                              //清除进位 
    result->sign =num1->sign;           //保存符号 
    //将被加数复制到结果数组中 
    for(i=0;i<num1->digit;i++)             
        result->num[i]=num1->num[i];
    //num2中的数小,可能位数也少些 
    for(i=0;i<num2->digit;i++)               
    {
        //将对应位的数和进位数相加 
        result->num[i]=result->num[i]+num2->num[i]+carry;    
        carry=result->num[i]/10;       //计算进位数据 
        result->num[i]=result->num[i]%10;     //保留一位 
    }
    if(carry)                       //若最后还有进位 
        result->num[i]=result->num[i]+carry;
    BigIntTrim(result);                //整理结果 
} 

减法运算
减法运算可以看做异号加法,结果的最大位数和较大的减数位数相同,可以把被减数缺少的位数用零补全然后相减,也可以只减到被减数的位数,然后将减数的高位直接写到结果的数组中。

这里写图片描述
实现代码:

void BigIntSub1(pBIGINT num1,pBIGINT num2,pBIGINT result)     
{
    int i,borrow;
    result->sign =num1->sign;         //结果符号 
    borrow=0;
    //将被减数的内容复制到结果中 
    for(i=0;i<num1->digit;i++)                
        result->num[i]=num1->num[i];
    for(i=0;i<=num2->digit;i++)
    {
        //num1减去num2,并减去低位的借位 
        result->num[i]=result->num[i]-num2->num[i]-borrow;                                           
        if(result ->num[i]<0)             //若为负数 
        {
            result->num[i]=10+result->num[i];    //向高位借位 
            borrow=1;                   //设置借位数 
        }else
            borrow=0;
    }
    if(borrow==1)
        result->num[i]=result->num[i]-borrow;
    i=num1->digit;
    while(i>0)
    {
        if(result->num[i]==0)
            i--;
        else
            break;
    } 
    result->digit=i+1;               //保存结果位数 
    BigIntTrim(result);              //整理结果 
} 

乘法运算
对于乘法运算,以乘法的每一位去乘以被乘数。例如,首先以乘数的个位去乘被乘数,将结果通过进位处理后保存到结果位中。接着用乘数的十位去乘以被乘数,将每位计算结果累加到最终结果中。

这里写图片描述
实现代码:
两个数相乘最大的位数是两个乘数的位数之和,在乘法中我们需要每执行一次乘法就要对数组进行进位的处理。

void BigIntMul(pBIGINT num1,pBIGINT num2,pBIGINT result)
{
    char carry,temp;
    int i,j,pos;
    //结果数组和中间数清0 
    for(i=0;i<num1->digit+num2->digit;i++)     
        result->num[i]=0;
    //用乘数的每一位乘以被乘数 
    for(i=0;i<num2->digit;i++)               
    {
        carry=0;                              //清除进位 
        //被乘数的每一位 
        for(j=0;j<num1->digit;j++)                  
        {
            //相乘并加上进位 
            temp=num2->num[i] * num1->num[j]+carry;    
             //计算进位carry 
            carry =temp/10; 
            //计算当前位的值                       
            temp=temp%10;                         
            pos=i+j;
            //计算结果累加到临时数组中 
            result->num[pos]+=temp;             
            carry=carry+result->num[pos]/10;           //计算进位 
            result->num[pos]=result->num[pos]%10; 
        }
        if(carry>0)
        {
            result->num[i+j]=carry;                //加上最高位进位 
            result->digit=i+j+1;                  //保存结果位数 
        }else
            result->digit=i+j;                   //保存结果位数 
    } 
    result->sign=num1->sign * num2->sign;        //结果的符号 
} 

除法运算
对于大数除法运算,首先取被除数的最高两位作为部分被除数,去除以除数,根据该部分被除数与除数的结果——商,得到一位数的商。
除法对数据有限制不能分母为零,分母为零没有意义;不能用小数除以大数

这里写图片描述
实现代码:
返回的结果是保存商的数组的指针,不包含余数。

void BigIntDiv(pBIGINT num1,pBIGINT num2,pBIGINT result,pBIGINT residue)
{
    BIGINT residol;
    int i,j,k,m;               //k保存试商结果,m保存商的位数 
    char t;
    result->sign = num1->sign * num2->sign;        //商的符号 
     //分配余数的内存空间
    residue->num =(char *)malloc(sizeof(char) * num2->digit);   
    for(i=0;i<residue->digit;i++)            //将余数全部清0 
        residue->num[i]=0;
    m=0;
    for(i=num1->digit-1;i>=0;i--)
    {
        //重新设置余数的位数比除数多一位 
        residue->digit=num2->digit+1;       
        for(j=num2->digit-1;j>0;j--)               //移余数 
            residue->num[j]=residue->num[j-1];
        //复制被除数中的一位到余数的最低位中 
        residue->num[0]=num1->num[i];          
        BigIntTrim(residue);                  //整理余数 
        k=0;                                      //试商 
         //比较余数与除数的大小 
        while(BigIntEqual(residue,num2)>=0)    
        {
            BigIntSub1(residue,num2,residue);     //用余数减去除数,差值保存在余数中 
            k++;                       //试商加1 
        } 
        result->num[m++]=k;           //保存商 
    }
    result->digit=m;                 //保存商的位数 
    for(i=0;i<m/2;i++)              //反转商的值            
    {
        t=result->num[i];
        result->num[i]=result->num[m-1-i];
        result->num[m-1-i]=t; 
    } 
    BigIntTrim(result);          //整理商 
    BigIntTrim(residue);            //整理余数 
 }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/184903.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • xshell安装步骤_Xshell怎么使用

    xshell安装步骤_Xshell怎么使用XShell可以在Windows界面下来访问远端不同系统下的服务器,从而比较好的达到远程控制终端的目的。它支持RLOGIN、SFTP、SERIAL、TELNET、SSH2和SSH1,可以非常方便的对Linux主机进行远程管理。除此之外,其还有丰富的外观配色方案以及样式选择。Xshell免费版官网下载地址https//www.xshell.com/zh/free-for-home-school/链接https//pan.baidu.com/s/1NJGWZHkByakOkQpKfkc7Yg。…

  • std::vector初始化[通俗易懂]

    std::vector初始化[通俗易懂]#include<iostream>#include<stdint.h>#include<vector>usingnamespacestd;intmain(){ std::vector<uint8_t>temp0(0,0); cout<<“vectorsize:”<<temp0.size()<<endl; std::vector<uint8_t>temp1(.

  • JavaScript设计模式—-策略模式[通俗易懂]

    JavaScript设计模式—-策略模式[通俗易懂]声明:这个系列为阅读《JavaScript设计模式与开发实践》—-曾探@著一书的读书笔记1.策略模式的定义将不变的部分和变化的部分隔开是每个设计模式的主题。定义一系列的算法,把它们一个个封装起来,并且使它们可以相互替换。2.策略模式的目的将算法的使用与算法的实现分离开来。3.传统语言中的策略模式和JavaScript中的策略模式对比3.1.传统语言中的策略模式使用策略模式来实现计算奖金v

  • VB学习的总体总结一

    VB学习的总体总结一经过对VB20天左右的学习,对其有了一定的了解。我觉得VB这种工具就是通过程序设计,做出软件。那么,可不可以用这种思想理解,VB的程序设计是怎么一步步进行的,给了我们一天主线。而在每一步中我们需要掌握什么,需要注意什么,思考怎么把每一步做的更好。然后就可以享受成果。 我对VB的整体总结为   VB工具就是一颗种子,设计步骤就是树干,步骤中的细节就是树叶,关键在于我们怎么让其枝繁

  • mysql连接池DruidDataSource的使用、配置「建议收藏」

    mysql连接池DruidDataSource的使用、配置「建议收藏」记录一下使用DruidDataSource的常用配置。1.pom.xml中引入:<!–https://mvnrepository.com/artifact/com.alibaba/druid–><dependency><groupId>com.alibaba</groupId&g…

  • ASF(传感器)

    ASF(传感器)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号