C语言实现大整数加减运算详解_C 语言

前言

    我们知道，在数学中，数值的大小是没有上限的，但是在计算机中，由于字长的限制，计算机所能表示的范围是有限的，当我们对比较小的数进行运算时，如：1234+5678，这样的数值并没有超出计算机的表示范围，所以可以运算。但是当我们在实际的应用中进行大量的数据处理时，会发现参与运算的数往往超过计算机的基本数据类型的表示范围，比如说，在天文学上，如果一个星球距离我们为100万光年，那么我们将其化简为公里，或者是米的时候，我们会发现这是一个很大的数。这样计算机将无法对其进行直接计算。

    可能我们认为实际应用中的大数也不过就是几百位而已，实际上，在某些领域里，甚至可能出现几百万位的数据进行运算，这是我们很难想象的。如果没有计算机，那么计算效率可想而知。

    由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。本项目实现了大数运算的加、减运算。

一. 问题提出

用C语言实现一个大整数计算器。初步要求支持大整数的加、减运算，例如8888888888888+1112=8888888890000或1000000000000-999999999999=1。

C语言中，整型变量所能存储的最宽数据为0xFFFF FFFF，对应的无符号数为4294967295，即无法保存超过10位的整数。注意，此处"10位"指数学中的10个数字，并非计算机科学中的10比特。浮点类型double虽然可以存储更多位数的整数，但一方面常数字面量宽度受编译器限制，另一方面通过浮点方式处理整数精度较低。例如：

  double a = 1377083362513770833626.0, b=1585054852315850548524.0;
  printf("res = %.0f\n", a+b);

输出为res = 2962138214829621510144，而正确值应为2962138214829621382150。

既然基本数据类型无法表示大整数，那么只能自己设计存储方式来实现大整数的表示和运算。通常，输入的大整数为字符串形式。因此，常见的思路是将大整数字符串转化为数组，再用数组模拟大整数的运算。具体而言，先将字符串中的数字字符顺序存入一个较大的整型数组，其元素代表整数的某一位或某几位(如万进制)；然后根据运算规则操作数组元素，以模拟整数运算；最后，将数组元素顺序输出。

数组方式操作方便，实现简单，缺点是空间利用率和执行效率不高。也可直接操作大整数字符串，从字符串末尾逆向计算。本文实现就采用这种方式。

二. 代码实现

首先，给出几个宏定义和运算结构：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ADD_THRES   (sizeof("4294967295")-2) //两个9位整数相加不会溢出
#define MUL_THRES   (sizeof("65535")-2)    //两个4位整数相乘不会溢出
#define OTH_THRES   (sizeof("4294967295")-1) //两个10位整数相减或相除不会溢出

typedef struct{
  char *leftVal;
  char *rightVal;
  char operator;
}MATH_OPER;

基于上述定义，以下将依次给出运算代码的实现。

加法运算主要关注相加过程中的进位问题：

void Addition(char *leftVal, char *rightVal,
       char *resBuf, unsigned int resbufLen) {
  unsigned int leftLen = strlen(leftVal);
  unsigned int rightLen = strlen(rightVal);

  unsigned char isLeftLonger = (leftLen>=rightLen) ? 1 : 0;
  unsigned int longLen = isLeftLonger ? leftLen : rightLen;
  if(resbufLen < longLen) { //possible carry + string terminator
    fprintf(stderr, "Not enough space for result(cur:%u)!\n", resbufLen);
    return;
  }

  char *longAddend = isLeftLonger ? leftVal : rightVal;
  char *shortAddend = isLeftLonger ? rightVal : leftVal;
  unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) : (rightLen-leftLen);
  //a carry might be generated from adding the most significant digit
  if((leftLen == rightLen) && (leftVal[0]-'0'+rightVal[0]-'0' >= 9))
    resBuf += 1;

  unsigned int carry = 0;
  int i = longLen-1;
  for(; i >= 0; i--) {
    unsigned int leftAddend = longAddend[i] - '0';
    unsigned int rightAddend = (i<diffLen) ? 0 : shortAddend[i-diffLen]-'0';
    unsigned int digitSum = leftAddend + rightAddend + carry;
    resBuf[i] = digitSum % 10 + '0';
    carry = (digitSum >= 10) ? 1 : 0;
  }
  if(carry == 1) {
    resBuf -= 1;
    resBuf[0] = '1';
  }
  else if(leftVal[0]-'0'+rightVal[0]-'0' == 9) {
    resBuf -= 1;
    resBuf[0] = ' '; //fail to generate a carry
  }
}

注意第33~36行的处理，当最高位未按期望产生进位时，原来为0的resBuf[0]被置为空格字符，否则将无法输出运算结果。当然，也可将resBuf整体前移一个元素。

减法运算相对复杂，需要根据被减数和减数的大小调整运算顺序。若被减数小于减数("11-111"或"110-111")，则交换被减数和减数后再做正常的减法运算，并且结果需添加负号前缀。此外，还需关注借位问题。

void Subtraction(char *leftVal, char *rightVal,
         char *resBuf, unsigned int resbufLen) {
  int cmpVal = strcmp(leftVal, rightVal);
  if(!cmpVal) {
    resBuf[0] = '0';
    return;
  }

  unsigned int leftLen = strlen(leftVal);
  unsigned int rightLen = strlen(rightVal);
  unsigned char isLeftLonger = 0;
  if((leftLen > rightLen) ||       //100-10
    (leftLen == rightLen && cmpVal > 0)) //100-101
    isLeftLonger = 1;
  unsigned int longLen = isLeftLonger ? leftLen : rightLen;
  if(resbufLen <= longLen) { //string terminator
    fprintf(stderr, "Not enough space for result(cur:%u)!\n", resbufLen);
    return;
  }

  char *minuend = isLeftLonger ? leftVal : rightVal;
  char *subtrahend = isLeftLonger ? rightVal : leftVal;
  unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) : (rightLen-leftLen);
  //a borrow will be generated from subtracting the most significant digit
  if(!isLeftLonger) {
    resBuf[0] = '-';
    resBuf += 1;
  }

  unsigned int borrow = 0;
  int i = longLen-1;
  for(; i >= 0; i--)
  {
    unsigned int expanSubtrahend = (i<diffLen) ? '0' : subtrahend[i-diffLen];
    int digitDif = minuend[i] - expanSubtrahend - borrow;
    borrow = (digitDif < 0) ? 1 : 0;
    resBuf[i] = digitDif + borrow*10 + '0';
    //printf("[%d]Dif=%d=%c-%c-%d -> %c\n", i, digitDif, minuend[i], expanSubtrahend, borrow, resBuf[i]);
  }

  //strip leading '0' characters
  int iSrc = 0, iDst = 0, isStripped = 0;
  while(resBuf[iSrc] !='\0') {
    if(isStripped) {
      resBuf[iDst] = resBuf[iSrc];
      iSrc++; iDst++;
    }
    else if(resBuf[iSrc] != '0') {
      resBuf[iDst] = resBuf[iSrc];
      iSrc++; iDst++;
      isStripped = 1;
    }
    else
      iSrc++;
   }
   resBuf[iDst] = '\0';
}

对于Addition()和Subtraction()函数，设计测试用例如下：

#include<assert.h>
#define ASSERT_ADD(_add1, _add2, _sum) do{\
  char resBuf[100] = {0}; \
  Addition(_add1, _add2, resBuf, sizeof(resBuf)); \
  assert(!strcmp(resBuf, _sum)); \
}while(0)
#define ASSERT_SUB(_minu, _subt, _dif) do{\
  char resBuf[100] = {0}; \
  Subtraction(_minu, _subt, resBuf, sizeof(resBuf)); \
  assert(!strcmp(resBuf, _dif)); \
}while(0)
void VerifyOperation(void) {
  ASSERT_ADD("22", "1686486458", "1686486480");
  ASSERT_ADD("8888888888888", "1112", "8888888890000");
  ASSERT_ADD("1234567890123", "1", "1234567890124");
  ASSERT_ADD("1234567890123", "3333333333333", "4567901223456");
  ASSERT_ADD("1234567890123", "9000000000000", "10234567890123");
  ASSERT_ADD("1234567890123", "8867901223000", "10102469113123");
  ASSERT_ADD("1234567890123", "8000000000000", " 9234567890123");
  ASSERT_ADD("1377083362513770833626", "1585054852315850548524", "2962138214829621382150");

  ASSERT_SUB("10012345678890", "1", "10012345678889");
  ASSERT_SUB("1", "10012345678890", "-10012345678889");
  ASSERT_SUB("10012345678890", "10012345678891", "-1");
  ASSERT_SUB("10012345678890", "10012345686945", "-8055");
  ASSERT_SUB("1000000000000", "999999999999", "1");
}

考虑到语言内置的运算效率应该更高，因此在不可能产生溢出时尽量选用内置运算。CalcOperation()函数便采用这一思路：

void CalcOperation(MATH_OPER *mathOper, char *resBuf, unsigned int resbufLen) {
  unsigned int leftLen = strlen(mathOper->leftVal);
  unsigned int rightLen = strlen(mathOper->rightVal);

  switch(mathOper->operator) {
    case '+':
      if(leftLen <= ADD_THRES && rightLen <= ADD_THRES)
        snprintf(resBuf, resbufLen, "%d",
             atoi(mathOper->leftVal) + atoi(mathOper->rightVal));
      else
        Addition(mathOper->leftVal, mathOper->rightVal, resBuf, resbufLen);
      break;
    case '-':
      if(leftLen <= OTH_THRES && rightLen <= OTH_THRES)
        snprintf(resBuf, resbufLen, "%d",
             atoi(mathOper->leftVal) - atoi(mathOper->rightVal));
      else
        Subtraction(mathOper->leftVal, mathOper->rightVal, resBuf, resbufLen);
      break;
    case '*':
      if(leftLen <= MUL_THRES && rightLen <= MUL_THRES)
        snprintf(resBuf, resbufLen, "%d",
             atoi(mathOper->leftVal) * atoi(mathOper->rightVal));
      else
        break; //Multiplication: product = multiplier * multiplicand
      break;
    case '/':
      if(leftLen <= OTH_THRES && rightLen <= OTH_THRES)
        snprintf(resBuf, resbufLen, "%d",
             atoi(mathOper->leftVal) / atoi(mathOper->rightVal));
      else
        break; //Division: quotient = dividend / divisor
      break;
    default:
      break;
  }

  return;
}

注意，大整数的乘法和除法运算尚未实现，因此相应代码分支直接返回。

最后，完成入口函数：

int main(void) {
  VerifyOperation();

  char leftVal[100] = {0}, rightVal[100] = {0}, operator='+';
  char resBuf[1000] = {0};

  //As you see, basically any key can quit:)
  printf("Enter math expression(press q to quit): ");
  while(scanf(" %[0-9] %[+-*/] %[0-9]", leftVal, &operator, rightVal) == 3) {
    MATH_OPER mathOper = {leftVal, rightVal, operator};
    memset(resBuf, 0, sizeof(resBuf));
    CalcOperation(&mathOper, resBuf, sizeof(resBuf));
    printf("%s %c %s = %s\n", leftVal, operator, rightVal, resBuf);
    printf("Enter math expression(press q to quit): ");
  }
  return 0;
}

上述代码中，scanf()函数的格式化字符串风格类似正则表达式。其详细介绍参见《sscanf的字符串格式化用法》一文。

三. 效果验证

将上节代码存为BigIntOper.c文件。测试结果如下：

[wangxiaoyuan_@localhost ~]$ gcc -Wall -o BigIntOper BigIntOper.c
[wangxiaoyuan_@localhost ~]$ ./BigIntOper
Enter math expression(press q to quit): 100+901
100 + 901 = 1001
Enter math expression(press q to quit): 100-9
100 - 9 = 91
Enter math expression(press q to quit): 1234567890123 + 8867901223000
1234567890123 + 8867901223000 = 10102469113123
Enter math expression(press q to quit): 1377083362513770833626 - 1585054852315850548524
1377083362513770833626 - 1585054852315850548524 = -207971489802079714898
Enter math expression(press q to quit): q
[wangxiaoyuan_@localhost ~]$

通过内部测试用例和外部人工校验，可知运算结果正确无误。

总结

以上就是C语言实现大整数加减运算的全部内容，大家都学会了吗？希望本文的内容对大家学习C语言能有所帮助。

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c语言
大整数加减法
c语言加减乘除运算、大整数加减法 c语言、c语言长整数四则运算、c语言位运算详解、大整数四则运算c语言，以便于您获取更多的相关知识。

时间： 2024-10-27 13:24:25

C语言实现大整数加减运算详解_C 语言的相关文章

C 语言指针变量的运算详解_C 语言

指针变量保存的是地址,本质上是一个整数,可以进行部分运算,例如加法.减法.比较等,请看下面的代码: #include <stdio.h> int main(){ int a = 10, *pa = &a, *paa = &a; double b = 99.9, *pb = &b; char c = '@', *pc = &c; //最初的值 printf("&a=%#X, pa=%#X, pb=%#X, pc=%#X\n", &

C语言中改变目录的相关操作函数详解_C 语言

C语言fchdir()函数:改变当前工作目录头文件: #include <unistd.h> 定义函数: int fchdir(int fd); 函数说明:fchdir()用来将当前的工作目录改变成以参数fd 所指的文件描述词. 返回值:执行成功则返回 0, 失败返回-1, errno 为错误代码. 范例 #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <

C语言 用指针作为函数返回值详解_C 语言

C语言允许函数的返回值是一个指针(地址),我们将这样的函数称为指针函数.下面的例子定义了一个函数 strlong(),用来返回两个字符串中较长的一个: #include <stdio.h> #include <string.h> char *strlong(char *str1, char *str2){ if(strlen(str1) >= strlen(str2)){ return str1; }else{ return str2; } } int main(){ cha

c语言字符数组与字符串的使用详解_C 语言

1.字符数组的定义与初始化字符数组的初始化,最容易理解的方式就是逐个字符赋给数组中各元素.char str[10]={ 'I',' ','a','m',' ','h','a','p','p','y'};即把10个字符分别赋给str[0]到str[9]10个元素如果花括号中提供的字符个数大于数组长度,则按语法错误处理:若小于数组长度,则只将这些字符数组中前面那些元素,其余的元素自动定为空字符(即 '\0' ). 2.字符数组与字符串在c语言中,将字符串作为字符数组来处理.(c++中不是)在实际应用

C语言运算符的优先级和结合性实例详解_C 语言

运算符是告诉编译程序执行特定算术或逻辑操作的符号.C语言的运算范围很宽,把除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理.主要分为三大类:算术运算符. 关系运算符与逻辑运算符.除此之外,还有一些用于完成特殊任务的运算符. 先来看一个例子: #include <stdio.h> int main(){ int a=10,b=1,c=2; a=b=c; printf( "12+3*5=%d\n", 12+3*5); printf( "a=%d, c=%

C语言双向链表的表示与实现实例详解_C 语言

1.概述: C语言中一种更复杂的链表是"双向链表"或"双面链表".其表中的每个节点有两个连接:一个指向前一个节点,(当这个"连接"为第一个"连接"时,指向空值或者空列表):而另一个指向下一个节点,(当这个"连接"为最后一个"连接"时,指向空值或者空列表) 一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接 在一些低级语言中, XOR-linking 提供一种在双向链表中

C语言位运算和sizeof运算符详解_C 语言

位运算和sizeof运算符       C语言中提供了一些运算符可以直接操作整数的位,称为位运算,因此位运算中的操作数都必须是整型的.位运算的效率是比较高的,而且位运算运用好的话会达到意想不到的效果.位运算主要有6种:与(&),或(|),取反(~),异或(^),左移(<<),右移(>>). 1.位运算中的类型转换       位运算都必须进行Integer Promotion.在进行运算之前,都必须将char型.short型的数据转换为int或者unsigned int型再

C/C++字符串函数之复制函数详解_C 语言

突然发现对字符串函数缺乏系统的了解,所以花了一点时间专门整理下,在此记录之,以方便自己及有需要的人使用. C/C++字符串函数的头文件:string.h 复制函数主要有4个,如下: 1.char * strcpy(char* destination,const char * source); 2.char* strncpy(char* destination,const char* source,size_t num); 3.void * memcpy(void* destination,con

C语言 经典题目螺旋矩阵 实例详解_C 语言

C语言 经典题目螺旋矩阵 //N阶螺旋矩阵 #include <stdio.h> #include <stdlib.h> int main() { int N,i,j,n,num=1; int a[10][10]={0}; printf("输入你要输出的几阶中断:"); scanf("%d",&N); for(n=0;n<=N/2;n++) { for(j=n;j<=N-n-1;j++) a[n][j]=num++; fo