2011년 2월 2일 수요일

C++ Big Integer Class 구현

code jam 문제를 풀다가 두고두고 쓰면 좋을 것같아서 class file을 만들었다.
하지만 허접하게 구현해서 몇가지 제약사항이 있다.

<주의사항>
1. 뺄셈 operator 사용시 호출인자가 더 큰값이어야 한다.(아닐경우 unhandling)
2. 나눗셈 미구현

#include<string>
#define SIZE 100

using namespace std;

class BigInteger
{
private:
 string num;
 int range; //배열사용범위 표시
 int number[SIZE]; // 배열 1칸에 4자리의 숫자(0001~9999)가 들어간다
 int go_up[SIZE+1]; // 사칙연산 후 올림을 위한 수가 저장된다.

public:
 BigInteger(string n);
 string getNum();
 int* getNumber();
 int getRange();
 void operator+(BigInteger bi);
 void operator-(BigInteger bi); //앞의 인자(호출인자)가 무조건 크다는 전제
 void operator*(BigInteger bi);
 void operator/(BigInteger bi); //미구현
};

BigInteger::BigInteger(string n)
{
 memset(number,0,sizeof(int)*SIZE);
 memset(go_up,0,sizeof(int)*SIZE);
 num = n;
 int insert0 = n.size()%4;
 string tmp;

 for(int i=0; i<(4-insert0); i++)
 {
  n.insert(0,"0");
 }
 int index = (n.size()-1)/4;
 range = index;
 for(int i=0; index>=0;i++, index--)
 {
  tmp = n.substr(4*i,4);
  number[index] = atoi(tmp.c_str());
 }
}
int BigInteger::getRange()
{
 return range;
}
int* BigInteger::getNumber()
{
 return number;
}
string BigInteger::getNum()
{
 string largeNum;
 char tmp[5];
 for(int i=0; i<=range; i++)
 {
  itoa(number[i],tmp,10);
  largeNum.insert(0,tmp);
 }
 return largeNum;
}
void BigInteger::operator+(BigInteger bi)
{
 int index = range;
 int* big = bi.getNumber();
 if(bi.getRange()>index) 
  index=bi.getRange();
 
 for(int i=0; i<index; i++)
 {
  number[i]= number[i] + big[i] + go_up[i];
  go_up[i+1] = number[i]/10000;
  number[i] = number[i]%10000;
 }
 //range 재조정
 for(int i=SIZE-1; i>=0; i--)
 {
  if(number[i]>0)
  {
   range=i;
   break;
  }
 }
 memset(go_up,0, sizeof(int)*100);
}
// 뺄셈시 앞의 big Integer가 무조건 크다는 가정임
void BigInteger::operator-(BigInteger bi)
{
 int index = range;
 int* big = bi.getNumber();
 if(bi.getRange()>index) 
  index=bi.getRange();
 
 for(int i=0; i<index; i++)
 {
  number[i]= number[i] - big[i];
  if( number[i] < 0) // 앞의 자리수에서 하나 꾸어 옴.
  {
   number[i+1]--;
   number[i] = number[i] + 10000;
  }
 }
 //range 재조정
 for(int i=SIZE-1; i>=0; i--)
 {
  if(number[i]>0)
  {
   range=i;
   break;
  }
 }
}
void BigInteger::operator*(BigInteger bi)
{
 memset(go_up,0, sizeof(int)*100);
 int index = range;
 int* big = bi.getNumber();
 int tmp[100];
 if(bi.getRange()>index) 
  index=bi.getRange();
 
 for(int i=0; i<range+1; i++)
 {
  for(int j=0; j<bi.getRange()+1; j++)
  {
   tmp[j] = number[j] * big[i];

   go_up[i+j+1] += (tmp[j]+go_up[i+j])/10000;
   go_up[i+j] = (tmp[j]+go_up[i+j])%10000;
  }
 }
 memcpy(number,go_up,sizeof(int)*100);
 //range 재조정
 for(int i=SIZE-1; i>=0; i--)
 {
  if(number[i]>0)
  {
   range=i;
   break;
  }
 }
 memset(go_up,0, sizeof(int)*100);
}

댓글 없음:

댓글 쓰기