C语⾔实现⼤整数加减运算详解
前⾔
我们知道，在数学中，数值的⼤⼩是没有上限的，但是在计算机中，由于字长的限制，计算机所能表⽰的范围是有限的，当我们对⽐较⼩的数进⾏运算时，如：1234+5678，这样的数值并没有超出计算机的表⽰范围，所以可以运算。但是当我们在实际的应⽤中进⾏⼤量的数据处理时，会发现参与运算的数往往超过计算机的基本数据类型的表⽰范围，⽐如说，在天⽂学上，如果⼀个星球距离我们为100万光年，那么我们将其化简为公⾥，或者是⽶的时候，我们会发现这是⼀个很⼤的数。这样计算机将⽆法对其进⾏直接计算。
可能我们认为实际应⽤中的⼤数也不过就是⼏百位⽽已，实际上，在某些领域⾥，甚⾄可能出现⼏百万位的数据进⾏运算，这是我们很难想象的。如果没有计算机，那么计算效率可想⽽知。
由于编程语⾔提供的基本数值数据类型表⽰的数值范围有限，不能满⾜较⼤规模的⾼精度数值计算，因此需要利⽤其他⽅法实现⾼精度数值的计算，于是产⽣了⼤数运算。本项⽬实现了⼤数运算的加、减运算。
⼀. 问题提出
⽤C语⾔实现⼀个⼤整数计算器。初步要求⽀持⼤整数的加、减运算，例如8888888888888+1112=88888
88890000或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--)string字符串转化数组
{
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()函数的格式化字符串风格类似正则表达式。其详细介绍参见⼀⽂。
三. 效果验证
将上节代码存为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语⾔能有所帮助。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论