#include <iostream> #include <stdio.h> #include <cstring> #include<cassert> #include <cmath> using namespace std; const int MaxShort = 100;//最多有MaxShort * 2个字节//如果要表示64位int,MaxShort = 4 const int baseNum = pow(2.0,16.0); const int Shift = 16; typedef unsigned short Unshort; typedef struct BigNum { int m_len; Unshort m_data[MaxShort]; }BigNum; BigNum CreateAbsBigNum(char *src)//低位放前,高位放后; { BigNum bg; Unshort *data = bg.m_data; int b = 0; while (src[0]!='\0') { int i = 0; int reminder = 0; while (src[i]!='\0') { int divident = src[i] - '0' + reminder * 10; reminder = divident % baseNum; src[i] = divident / baseNum + '0'; ++i; } data[b++] = reminder; while (*src =='0') ++src; } bg.m_len = b; return bg; } BigNum AbsMinus(BigNum &bg1,BigNum &bg2)//bg1 >bg2 { int left = bg1.m_len; int right = bg2.m_len; int carry = 0; BigNum bg; for (int i=0;i<right;++i) { int tmp = bg1.m_data[i] - bg2.m_data[i] - carry; if(tmp<0) { carry = 1; bg.m_data[i] = baseNum + tmp; } else { bg.m_data[i] = tmp; carry = 0; } } for (int i= right;i<left;++i) { int tmp = bg1.m_data[i] - carry; if (tmp <0) { carry = 1; bg.m_data[i] = baseNum +tmp; } else { bg.m_data[i] = tmp; carry = 0; } } bg.m_len = left; while (bg.m_len>=0 && bg.m_data[bg.m_len -1]==0) { --bg.m_len; } return bg; } BigNum AbsAdd(BigNum &bg1,BigNum &bg2) { int left = bg1.m_len; int right = bg2.m_len; int size = left; int maxLen = right; BigNum *bgmax = &bg2; if(size>right) { size = right; maxLen = left; bgmax = &bg1; } int carry = 0; BigNum bg; for (int i=0;i<size;++i) { int tmp = bg1.m_data[i] + bg2.m_data[i] + carry; //carry = tmp /baseNum; carry = tmp>>Shift; //bg.m_data[i] = tmp &(1<<Shift - 1); bg.m_data[i] = tmp & 0xffff; } for (int i = size;i<maxLen;++i) { int tmp = bgmax->m_data[i] + carry; carry = tmp>>Shift; //carry = tmp /baseNum; //bg.m_data[i] = tmp &(1<<Shift - 1); bg.m_data[i] = tmp & 0xffff; } if (carry) { bg.m_data[maxLen] = 1; ++maxLen; } bg.m_len = maxLen; return bg; } BigNum AbsMul(BigNum &bg1,BigNum &bg2) { BigNum bg; memset(bg.m_data,0,sizeof(bg.m_data)); int i,j; for (i=0;i<bg1.m_len;++i) { size_t carry = 0; for (j=0;j <bg2.m_len;++j) { size_t tmp = bg.m_data[i+j] + bg1.m_data[i] * bg2.m_data[j] + carry; bg.m_data[i+j] = tmp %baseNum; carry = tmp /baseNum; } if (carry >0) { bg.m_data[i+j] += carry; } } if(bg.m_data[bg1.m_len+bg2.m_len -1] > 0) bg.m_len = bg1.m_len+bg2.m_len; else bg.m_len = bg1.m_len+bg2.m_len -1; return bg; } void GetAbsDecNum(BigNum &bg,char *tgt) { int size = bg.m_len; Unshort *data = bg.m_data; int b=0; while (size>0) { int i = size - 1; int reminder = 0; while (i>=0) { int divident = data[i] + reminder * baseNum; reminder = divident % 10; data[i] = divident /10; --i; } tgt[b++] = reminder + '0'; while(size>0 && data[size -1]==0) --size; } tgt[b] = '\0'; } void Reverse(char *src) { int size = strlen(src); int beg = size/2 -1; for (;beg>=0;--beg) { int sym = size -beg -1; char tmp = src[beg]; src[beg] = src[sym]; src[sym] = tmp; } } int main() { char t[100]; memset(t,0,sizeof(t)); char s[] = "6430006453235007"; BigNum bg = CreateAbsBigNum(s); //GetAbsDecNum(bg,t); //Reverse(t); //cout<<t<<endl; memset(t,0,sizeof(t)); char s1[]="1234567932211123423411431421246"; BigNum bg1 = CreateAbsBigNum(s1); //GetAbsDecNum(bg1,t); //Reverse(t); //cout<<t<<endl; BigNum bg2 = AbsMul(bg1,bg); memset(t,0,sizeof(t)); GetAbsDecNum(bg2,t); Reverse(t); cout<<t<<endl; }
主要思想就是用一个单位譬如char,int,short表示一个进制。譬如,对short而言,最大能表示的进制是2^16
还差除法没有写,主要是参考:http://blog.chinaunix.net/uid-26750235-id-3129246.html
可以考虑用一个int表示进制为10000,这样更方便