willsun888
9/18/2013 - 2:52 PM

大整数运算

大整数运算

//大整数运算
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//字符串反转
void strrev(char* s)
{
    int i=-1;
    while(s[++i]!='\0');
    for(int j=0;j<i/2;j++){
        char tmp = s[j];
        s[j] = s[i-j-1];
        s[i-j-1]=tmp;
    }
}
void Add(const char*str1, const char* str2, char* ans)
{
    int l1, l2, l;
    l1 = strlen(str1);
    l2 = strlen(str2);
    l = l1>l2 ? l1 : l2;
    char* s1 = (char*)malloc(sizeof(char)*(l1+1));
    char* s2 = (char*)malloc(sizeof(char)*(l2+1));
    memcpy(s1,str1,(l1+1)*sizeof(char));
    memcpy(s2,str2,(l2+1)*sizeof(char));
    strrev(s1);
    strrev(s2);
    int i;
    int sum, carry;
    i=sum=carry=0;
    while(i<l){
        char a = i<l1?s1[i]:'0';
        char b = i<l2?s2[i]:'0';
        sum = a-'0'+b-'0' + carry;
        ans[i] = sum % 10 + '0';
        carry = sum / 10;
        i++;
    }
    if(carry!=0)
        ans[i++]=carry+'0';
    ans[i]='\0';
    strrev(ans);
    free(s1);
    free(s2);
}
void Mul(const char*str1, const char* str2, char* ans)
{
    int l1, l2, l;
    l1 = strlen(str1);
    l2 = strlen(str2);
    l = l1 + l2;
    ans[0]='\0';
    char* s1 = (char*)malloc(sizeof(char)*(l1+1));
    char* s2 = (char*)malloc(sizeof(char)*(l2+1));
    memcpy(s1,str1,(l1+1)*sizeof(char));
    memcpy(s2,str2,(l2+1)*sizeof(char));
    strrev(s1);
    strrev(s2);
    char* tmp = (char*)malloc(sizeof(char)*(l1+2));
    int s, carry;
    s = carry = 0;
    for(int i=0;i<l2;i++){
        int j;
        for(int j=0;j<i;j++)
            tmp[j]='0';
        for(j=0;j<l1;j++){
            s = (s1[j]-'0')*(s2[i]-'0')+carry;
            tmp[i+j]=s%10+'0';
            carry=s/10;
        }
        if(carry!=0)
            tmp[i+j++]=carry+'0';
        tmp[i+j]='\0';
        strrev(ans);
        strrev(tmp);
        Add(ans,tmp, ans);
        strrev(ans);
    }
    strrev(ans);
}
int main()
{
    const char a[] = "12345";
    const char b[] = "123";
    char c[1024];

    Add(a,b,c);
    printf("a+b=%s\n", c);
    Mul(a,b,c);
    printf("a*b=%s\n", c);

    return 0;
}