c语⾔为正数⽆限⼤,⽆限⼤整数相加算法的C语⾔源代码
#include #include#include#include
#define MAXNUM 1000000000000000000
/*存储数据⽤的结构
long int型指针(Number)指向⼀个long int 数组，索引值最底的位，
为10进制数的最低18位。依次类推。
int型数值(Length)为数组的长度。
因为数组长度受int型最⼤值的限制，所以这个算法也不能真正实现“⽆限”。*/
structBigInt{long long*Number;intLength;
};void PrintBigInt(BigInt*bigNumber);long long pow(int x, inty);
BigInt* MakeBigIntFromString(char*bigIntString);void DeleteBigInt(BigInt*bigNumber);
BigInt* Add2BigInt(BigInt* n1, BigInt*n2);voidmain(){char* numberStr = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 numberStr2 = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
源代码大电影BigInt* bn =MakeBigIntFromString(numberStr);
BigInt* bn2 =MakeBigIntFromString(numberStr2);doubletstart, tend, tcost;
tstart=clock();
PrintBigInt(bn);
PrintBigInt(bn2);for (int i = 0; i < 1000; i++){
BigInt* result =Add2BigInt(bn, bn2);//PrintBigInt(result);
DeleteBigInt(result);
}
DeleteBigInt(bn);
DeleteBigInt(bn2);
tend=clock();
tcost= (double)(tend - tstart) /CLOCKS_PER_SEC;
printf("%lf\n", tcost);
}
BigInt* Add2BigInt(BigInt* n1, BigInt*n2){int maxLength = n1->Length;if (maxLength < n2->Length){
maxLength= n2->Length;
}/*加法只可能产⽣1位的进位，所以，只需要创建⼀个和最⼤长度相同的。*/BigInt* nOut = (BigInt*)malloc(sizeof(BigInt));
nOut->Length =maxLength;
nOut->Number = (long long*)malloc(sizeof(long long)* nOut->Length);for (int i = 0; i < nOut->Length; i++){
nOut->Number[i] = 0;
}for (int i = 0; i < nOut->Length; i++){if (n1->Length >i){
nOut->Number[i] += n1->Number[i];
}if (n2->Length >i){
nOut->Number[i] += n2->Number[i];
}/*处理进位。最⾼位不需要处理。*/
if (i != (nOut->Length - 1)){if (nOut->Number[i] >=MAXNUM){
nOut->Number[i] -=MAXNUM;
nOut->Number[i + 1] = 1;
}
}
}returnnOut;
}/*从⾼到低显⽰数值
不考虑单个long long数据超出18位的情况。*/
void PrintBigInt(BigInt*bigNumber){if (bigNumber ==NULL){return;
}if (bigNumber->Length < 1){return;
}int length = bigNumber->Length - 1;for (int i = length; i >= 0; i--){if (i !=length){if (bigNumber->Number[i] == 0){ printf("000000000000000000");
}else{
printf("%018lld", bigNumber->Number[i]);
}
}else{if ((*bigNumber).Number[i] != 0){
printf("%lld", bigNumber->Number[i]);
}
}
}
printf("\n");
}/*把字符串表⽰的数值格式化为BigInt型的结构
字符串结束位置⽤\0表⽰。*/BigInt* MakeBigIntFromString(char*bigIntString){/*获取字符串长度*/
int cLength =strlen(bigIntString);
BigInt* outBigInt = (BigInt*)malloc(sizeof(BigInt));if (cLength % 18 != 0){
outBigInt->Length = cLength / 18 + 1;
}else{
outBigInt->Length = cLength / 18;
}if (outBigInt->Length == 0){
outBigInt->Length == 1;
outBigInt->Number = (long long *)malloc(sizeof(long long));
outBigInt->Number[0] = 0;returnoutBigInt;
}
outBigInt->Number = (long long *)malloc(sizeof(long long)* outBigInt->Length);for (int i = 0; i < outBigInt->Length; i++){ outBigInt->Number[i] = 0;
}int powNum = 0;int numPos = 0;for (int i = cLength - 1; i >= 0; i--){
powNum= (cLength - 1 - i) % 18;
numPos= (cLength - 1 - i) / 18;
outBigInt->Number[numPos] += (bigIntString[i] - 48) * pow(10, powNum);
}returnoutBigInt;
}/*简单的幂函数
x y 都必须为正整数*/
long long pow(int x, inty){if (x == 0 || x < 0 || y < 0){return 0;
}if (x == 1 || y == 0){return 1;
}long long outNum =x;for (int i = 1; i < y; i++){
outNum= outNum *x;
}returnoutNum;
}void DeleteBigInt(BigInt*bigNumber){if (bigNumber !=NULL){if (bigNumber->Number !=NULL){free(bigNumber->Number); }free(bigNumber);
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。