다시 건드려보는 bigint class 제작

#include <stdlib.h> #include <stdio.h> #include <memory.h> class bigint { private: //모든 비트를 사용하기때문에 보수사용하면 오류날 것 같아서.. char sign; //+:0, -:1 unsigned *dats; //가장 뒷자리가 dats[0]에 저장 unsigned len; //dats배열 길이 public: bigint(); bigint(int); bigint(bigint &); unsigned resize(unsigned); //길이조절 unsigned resize(); //앞의 0 지우기 bigint abs(); //절대값 bigint negative(unsigned); //1의보수 int cmp(bigint &b); //strcmp와 리턴값 같음 bigint add(bigint &b); //this에 (this+b)를 저장 bigint sub(bigint &b); //this에 (this-b)를 저장 bigint shr(unsigned n); //this에 (this>>n)을 저장 bigint shl(unsigned n); //this에 (this<<n)을 저장 bigint mul_lr(bigint &b); //this에 (this*b)를 저장, A la russe알고리즘 void con2();//2진수 출력 }; bigint::bigint() { len=1; sign=0; dats=(unsigned*)calloc(1,sizeof(unsigned)); } bigint::bigint(int src) { len=1; sign=0; dats=(unsigned*)calloc(1,sizeof(unsigned)); dats[0]=src; if(src<0) sign=1, dats[0]*=-1; } bigint::bigint(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); 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::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); //dats[i]=carry&(~(1<<32)) carry>>=32; } for(; carry; i++) { carry=(long long)dats[i] + carry; dats[i]=carry&(((long long)1<<32)-1); //dats[i]=carry&(~(1<<32)) carry>>=32; } resize(); //0지우기 return *this; } //1의 보수 사용 bigint bigint::sub(bigint &b) { bigint subtrahend(b); //감수 resize(len); 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::shr(unsigned n) { unsigned move=n>>5, cut=n&31, i; dats[0]=dats[move]>>cut; for(i=1; i<len-move; i++) { dats[i-1]|=dats[i+move]<<(32-cut); dats[i]=dats[i+move]>>cut; } resize(len-move);//옮겨진 부분 삭제 resize(); //앞의 0자르기 return *this; } bigint bigint::shl(unsigned n) { unsigned move=n>>5, cut=n&31, i; resize(len+move+1); dats[len-1]=dats[len-move-1]<<cut; for(i=len-2; (int)i>=(int)move; i--) { dats[i+1]=dats[i+1]|(dats[i-move]>>(32-cut)); dats[i]=dats[i-move]<<cut; } memset(dats, 0, sizeof(unsigned)*move);//뒤에 옮겨진 부분 0으로 resize();//앞의0자르기 return *this; } 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); } *this=sum; return *this; } void bigint::con2() { int i, j; printf("%c","+-"[sign]); for(i=len-1; i>=0; i--) { for(j=31; j>=0; j--) { printf("%d", ((unsigned)dats[i]&(1<<j)) >>j ); } } printf("\n"); } int main() { /*bigint a(4294967295); bigint b(4294967295); a.con32(); b.con32(); a.add(b); a.con32();*/ /*int i; bigint a(1); for(i=0; i<50000; i++) { a.add(a); } a.con32();*/ /*bigint a(4294967294); bigint b(4294967295); a.con32(); b.con32(); a.sub(b); a.con32();*/ /*unsigned i; bigint a(1); a.con2(); for(i=1; i<64; i++) { a.shl(1); a.con2(); } for(i=1; i<64; i++) { a.shr(1); a.con2(); }*/ bigint a(123); bigint b(7); a.mul_lr(b); a.con2(); return 0; }

2^32진수쓰니까 많이 빠르네요.

10진수 출력 어떡하죠