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

  ", a+b);

  输出为,而正确值应为2962138214829621382150。

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

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

  二. 代码实现

  首先,给出几个宏定义和运算结构:

  #include

  #include

  #include

  #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:ಇ", 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

  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:ಇ", 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

  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

  ", 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';

  }

  对于和函数,设计测试用例如下:

  #include

  #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");

  }

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

  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

  ", leftVal, operator, rightVal, resBuf);

  printf("Enter math expression(press q to quit): ");

  }

  return 0;

  }

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

  三. 效果验证

  将上节代码存为文件。测试结果如下:

  [wangxiaoyuan_@localhost ~]$ gcc -Wall -o BigIntOper BigIntOper.c

  [wangxiaoyuan_@localhost ~]$ http://www.jb51.net/article/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语言能有所帮助。

  您可能感兴趣的文章: