bigint class 완성

#include <iostream> #include <string> #include <stdlib.h> #include <stdio.h> #include <memory.h> class bigint { private: char sign; //+:0, -:1 unsigned *dats; //가장 뒷자리가 dats[0]에 저장 unsigned len; //dats배열 길이 public: unsigned cona2u(char*); bigint(); ~bigint(); bigint(const int); bigint(const char*); bigint(const bigint &); unsigned resize(unsigned); //길이조절 unsigned resize(); //앞의 0 지우기 bigint abs(); //절대값 bigint negative(unsigned); //1의보수 int cmp(bigint &b); //strcmp와 리턴값 같음 bigint _or(bigint &b); //this에 저장 bigint _and(bigint &b); //this에 저장 bigint _xor(bigint &b); //this에 저장 bigint shr(unsigned n); //this에 (this>>n)을 저장 bigint shl(unsigned n); //this에 (this<<n)을 저장 bigint add(bigint &b); //this에 (this+b)를 저장, 리턴 bigint sub(bigint &b); //this에 (this-b)를 저장, 리턴 bigint mul(bigint &b); //(this*b)를 리턴 bigint mul_lr(bigint &b); //(this*b)를 리턴, A la russe알고리즘, 느려 bigint div(bigint &b, int); //(this/b)또는 (this%b)리턴 std::string con10(); //10진수변환 bigint operator=(const int); bigint operator=(const bigint &); bigint operator=(const char*); friend bigint operator-(bigint); friend bigint operator|(bigint, bigint); friend bigint operator&(bigint, bigint); friend bigint operator^(bigint, bigint); friend bigint operator+(bigint, bigint); friend bigint operator-(bigint, bigint); friend bigint operator*(bigint, bigint); friend bigint operator/(bigint, bigint); friend bigint operator%(bigint, bigint); friend bigint operator<<(bigint, bigint); friend bigint operator>>(bigint, bigint); friend bool operator<(bigint, bigint); friend bool operator<=(bigint, bigint); friend bool operator>(bigint, bigint); friend bool operator>=(bigint, bigint); friend bool operator==(bigint, bigint); friend bool operator!=(bigint, bigint); bigint operator|=(bigint); bigint operator&=(bigint); bigint operator^=(bigint); bigint operator+=(bigint); bigint operator-=(bigint); bigint operator*=(bigint); bigint operator/=(bigint); bigint operator%=(bigint); bigint operator<<=(bigint); bigint operator>>=(bigint); bigint operator++(); bigint operator++(int dummy); bigint operator--(); bigint operator--(int dummy); friend std::ostream& operator <<( std::ostream& os, bigint b ); friend std::istream& operator >>( std::istream& is, bigint& b ); }; unsigned bigint::cona2u(char *src) { unsigned ten, sum, eos=strlen(src)-1; for(sum=0, ten=1; (int)eos>=0 && ten<=100000000; ten*=10, eos--) { sum+=ten*(src[eos]-'0'); src[eos]=0; } return sum; } bigint::bigint() { len=1; sign=0; dats=(unsigned*)calloc(1,sizeof(unsigned)); } bigint::~bigint() { free(dats); } bigint::bigint(const int src) { len=1; sign=0; dats=(unsigned*)malloc(sizeof(unsigned)*len); dats[0]=src; } bigint::bigint(const char *src) { char *str=(char*)malloc(sizeof(char)*(strlen(src)+1)); sign=0; strcpy(str, src); if(src[0]=='-') strcpy(str,src+1), sign=1; if(src[0]=='+') strcpy(str,src+1); len=(strlen(src)-1)/9 + 1; dats=(unsigned*)malloc(sizeof(unsigned)*len); unsigned i; for(i=0; i<len; i++) { dats[i]=cona2u(str); } free(str); shl(len*32); unsigned j, lmt=len/2; for(i=(len/2)*32; i; i--) { shr(1); for(j=len-1; j>=lmt; j--) { if(dats[j]>=2147483648) dats[j]-=1647483648; } } } bigint::bigint(const bigint &src) { len=src.len; sign=src.sign; dats=(unsigned*)malloc(sizeof(unsigned)*len); memcpy(dats, src.dats, sizeof(unsigned)*len); } unsigned bigint::resize(unsigned len_new) { if(len==len_new) return len; unsigned *new_p=(unsigned*)malloc(sizeof(unsigned)*len_new); // memcpy(new_p, dats, sizeof(unsigned)*((len<len_new)?len:len_new)); //이부분에 realloc(dats, sizeof(unsigned)*len_new)쓰면 왜 값이 바뀌나요 free(dats); // dats=new_p; // if(len < len_new) memset(dats+len, 0, sizeof(unsigned)*(len_new-len)); len=len_new; return len; } unsigned bigint::resize() { unsigned i; for(i=len-1; dats[i]==0; i--); i++; if(i) resize(i); else resize(1); return len; } bigint bigint::abs() { bigint toreturn(*this); toreturn.sign=0; return toreturn; } //1의 보수 bigint bigint::negative(unsigned len_new) { bigint toreturn(*this); toreturn.resize(len_new); for(unsigned i=0; i<len_new; i++) toreturn.dats[i]=~toreturn.dats[i]; return toreturn; } int bigint::cmp(bigint &b) { if(sign==1 && b.sign==0) return -1; if(sign==0 && b.sign==1) return 1; int left=1, right=-1; if(sign==1 && b.sign==1) left=-1, right=1; if(len>b.len) return left; if(len<b.len) return right; for(int i=len-1; i>=0; i--) { if(dats[i]>b.dats[i]) return left; if(dats[i]<b.dats[i]) return right; } return 0; } bigint bigint::_or(bigint &b) { if(len<b.len) resize(b.len); unsigned i; for(i=0; i<b.len; i++) dats[i]|=b.dats[i]; return *this; } bigint bigint::_and(bigint &b) { if(len<b.len) resize(b.len); unsigned i; for(i=0; i<b.len; i++) dats[i]&=b.dats[i]; return *this; } bigint bigint::_xor(bigint &b) { if(len<b.len) resize(b.len); unsigned i; for(i=0; i<b.len; i++) dats[i]^=b.dats[i]; return *this; } bigint bigint::shr(unsigned n) { unsigned move=n>>5, cut=n&31, i, j, tmp; dats[0]=dats[move]>>cut; for(i=1; i<len-move; i++) { for(j=0, tmp=dats[i+move]; j<32-cut; j++) //dats[i+1]=dats[i+1]|(dats[i+move]<<(32-cut)); tmp<<=1; // dats[i-1]|=tmp; dats[i]=dats[i+move]>>cut; } resize(len-move);//옮겨진 부분 삭제 resize(); return *this; } bigint bigint::shl(unsigned n) { unsigned move=n>>5, cut=n&31, i, j, tmp; resize(len+move+1); dats[len-1]=dats[len-move-1]<<cut; for(i=len-2; (int)i>=(int)move; i--) { for(j=0, tmp=dats[i-move]; j<32-cut; j++) //dats[i+1]=dats[i+1]|(dats[i-move]>>(32-cut)); tmp>>=1; // dats[i+1]=dats[i+1]|tmp; dats[i]=dats[i-move]<<cut; } memset(dats, 0, sizeof(unsigned)*move);//뒤에 옮겨진 부분 0으로 resize(); return *this; } bigint bigint::add(bigint &b) { long long carry=0; unsigned i; resize( ((b.len>len)?b.len:len) + 1 ); for(i=0; i<b.len; i++) { carry = (long long)dats[i] + (long long)b.dats[i] + carry; dats[i]=carry&(((long long)1<<32)-1); carry>>=32; } for(; carry; i++) { carry=(long long)dats[i] + carry; dats[i]=carry&(((long long)1<<32)-1); carry>>=32; } resize(); return *this; } //1의 보수 사용 bigint bigint::sub(bigint &b) { bigint subtrahend(b); //감수 unsigned len_new=((len>b.len)?len:b.len); subtrahend=subtrahend.negative(len_new); add(subtrahend); if(len > len_new)//자리올림수있으면 { resize(len_new); add((bigint)1); } else//자리올림수 없으면 { *this=negative(len_new); sign=1; } return *this; } bigint bigint::mul(bigint &b) { bigint result, tmp; unsigned i, j; long long carry; for(i=0; i<b.len; i++) { tmp.resize(len+1+i); for(carry=j=0; j<len; j++) { carry=(long long)dats[j]*(long long)b.dats[i]+carry; tmp.dats[j+i]=(unsigned)carry&(((long long)1<<32)-1); carry>>=32; } tmp.dats[j+i]=(unsigned)carry; result.add(tmp); memset(tmp.dats, 0, sizeof(unsigned)*tmp.len); } result.resize(); return result; } bigint bigint::mul_lr(bigint &b) { bigint sum(0), tmp(b); while( cmp((bigint)0) != 0) { if(dats[0]&1) sum.add(tmp); shr(1); tmp.shl(1); } return sum; } bigint bigint::div(bigint &b, int ask_mod=0) { bigint r=abs(), q=0, divisor=b.abs(), one=1; unsigned i; for(i=0;divisor.cmp(r)<=0;divisor.shl(1),i++); i--; if((int)i>0) { one.shl(i); divisor.shr(1); while(b.cmp(r)<=0)//b<=r { for(;divisor.cmp(r)>0;divisor.shr(1),one.shr(1)); q._or(one); r.sub(divisor); } } if(ask_mod) return r; return q; } std::string bigint::con10() { bigint tmp(*this); unsigned i, j, lmt=tmp.len; char str_tmp[10]; std::string result; for(i=tmp.len*32; i; i--) { for(j=tmp.len-1; j>=lmt; j--) { if(tmp.dats[j] >= 500000000) tmp.dats[j]+=1647483648; } tmp.shl(1); } i=tmp.len-1; sprintf(str_tmp,"%u", tmp.dats[i]); result.insert(result.size(), str_tmp); if(i) { for(--i; i>=lmt; i--) { sprintf(str_tmp,"%09u",tmp.dats[i]); result.insert(result.size(), str_tmp); } } return result; } bigint bigint::operator=(const int src) { resize(1); sign=0; dats[0]=src; if(src<0) sign=1, dats[0]*=-1; return *this; } bigint bigint::operator=(const bigint &src) { resize(src.len); sign=src.sign; memcpy(dats, src.dats, sizeof(unsigned)*len); return *this; } bigint bigint::operator=(const char *src) { char *str=(char*)malloc(sizeof(char)*(strlen(src)+1)); sign=0; strcpy(str, src); if(src[0]=='-') strcpy(str,src+1), sign=1; if(src[0]=='+') strcpy(str,src+1); resize((strlen(src)-1)/9 + 1); unsigned i; for(i=0; i<len; i++) { dats[i]=cona2u(str); } free(str); shl(len*32); unsigned j, lmt=len/2; for(i=(len/2)*32; i; i--) { shr(1); for(j=len-1; j>=lmt; j--) { if(dats[j]>=2147483648) dats[j]-=1647483648; } } return *this; } bigint operator-(bigint a) { a.sign^=1; return a; } bigint operator|(bigint a, bigint b) { return a._or(b); } bigint operator&(bigint a, bigint b) { return a._and(b); } bigint operator^(bigint a, bigint b) { return a._xor(b); } bigint operator+(bigint a, bigint b) { if(a.sign==b.sign) return a.add(b); if(a.sign==0 && b.sign==1) return a.sub(b); //a.sign==1 && b.sign==0 return b.sub(a); } bigint operator-(bigint a, bigint b) { if(a.sign==1 && b.sign==1) { b.sign=0; if((a.abs()).cmp(b.abs())==1) b.sign=1; b.sub(a); return b; } if(a.sign==0 && b.sign==0) return a.sub(b); if(a.sign==0 && b.sign==1) return a.add(b); //a.sign==1 && b.sign==0 a.add(b); a.sign=1; return a; } bigint operator*(bigint a, bigint b) { bigint toreturn=a.mul(b); toreturn.sign=a.sign^b.sign; return toreturn; } bigint operator/(bigint a, bigint b) { bigint toreturn=a.div(b); toreturn.sign=a.sign^b.sign; return toreturn; } bigint operator%(bigint a, bigint b) { bigint toreturn=a.div(b,1); toreturn.sign=a.sign; return toreturn; } bigint operator<<(bigint a, bigint b) { bigint tmp(2147483647); while(b.len>1) { a.shl(2147483647); b.sub(tmp); } a.shl(b.dats[0]); return a; } bigint operator>>(bigint a, bigint b) { bigint tmp(2147483647); while(b.len>1) { a.shr(2147483647); b.sub(tmp); } a.shr(b.dats[0]); return a; } bool operator<(bigint a, bigint b) { if(a.cmp(b)<0) return true; return false; } bool operator<=(bigint a, bigint b) { if(a.cmp(b)<=0) return true; return false; } bool operator>(bigint a, bigint b) { if(a.cmp(b)>0) return true; return false; } bool operator>=(bigint a, bigint b) { if(a.cmp(b)>=0) return true; return false; } bool operator==(bigint a, bigint b) { if(a.cmp(b)==0) return true; return false; } bool operator!=(bigint a, bigint b) { if(a.cmp(b)==0) return false; return true; } bigint bigint::operator|=(bigint b) { if(len!=b.len) { resize((len>b.len)?len:b.len); b.resize((len>b.len)?len:b.len); } _or(b); resize(); return *this; } bigint bigint::operator&=(bigint b) { if(len!=b.len) { resize((len>b.len)?len:b.len); b.resize((len>b.len)?len:b.len); } _and(b); resize(); return *this; } bigint bigint::operator^=(bigint b) { if(len!=b.len) { resize((len>b.len)?len:b.len); b.resize((len>b.len)?len:b.len); } _xor(b); resize(); return *this; } bigint bigint::operator+=(bigint b) { if(sign==b.sign) return add(b); if(sign==0 && b.sign==1) return sub(b); //a.sign==1 && b.sign==0 return *this=b.sub(*this); } bigint bigint::operator-=(bigint b) { if(sign==1 && b.sign==1) { b.sign=0; if((abs()).cmp(b.abs())==1) b.sign=1; return *this=b.sub(*this); } if(sign==0 && b.sign==0) return sub(b); if(sign==0 && b.sign==1) return add(b); //a.sign==1 && b.sign==0 sign=1; return add(b); } bigint bigint::operator*=(bigint b) { char tmp=sign; *this=mul(b); sign=tmp^b.sign; return *this; } bigint bigint::operator/=(bigint b) { *this=div(b); sign=sign^b.sign; return *this; } bigint bigint::operator%=(bigint b) { *this=div(b,1); return *this; } bigint bigint::operator<<=(bigint b) { bigint tmp(2147483647); while(b.len>1) { shl(2147483647); b.sub(tmp); } shl(b.dats[0]); return *this; } bigint bigint::operator>>=(bigint b) { bigint tmp(2147483647); while(b.len>1) { shr(2147483647); b.sub(tmp); } shr(b.dats[0]); return *this; } bigint bigint::operator++() { *this+=1; return *this; } bigint bigint::operator++(int dummy) { bigint old(*this); *this+=1; return old; } bigint bigint::operator--() { *this-=1; return *this; } bigint bigint::operator--(int dummy) { bigint old(*this); *this-=1; return old; } std::ostream& operator<<(std::ostream& os, bigint b) { os<<"+-"[b.sign]<<b.con10(); return os; } std::istream& operator>>(std::istream& is, bigint& b) { std::string numstr; is>>numstr; b=numstr.c_str(); return is; } void fac(bigint n) { bigint result=1; for(; n>0; n--) result*=n; std::cout<<result<<"\n"; } int main() { bigint n=1; std::cin>>n; while(n>0) { fac(n); std::cin>>n; } return 0; }

10000팩토리얼 구하는데는 2초인데 출력하는데 1분????

BCD최적화 어쩌죠