지환태 :: ...

c++ bigint class완성

from Programming/bigint 2009/12/20 17:49

적분형님따라 만든 bigint

#include <iostream>
#include <fstream>
#include <string>  
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <time.h>

#pragma warning(disable:4996)

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 unsigned);
	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+b)를 리턴
	bigint sub(bigint &b);		//(this-b)를 리턴
	bigint mul(bigint &b);		//(this*b)를 리턴
	bigint div(bigint &b, int);	//(this/b)또는 (this%b)리턴

std::string conbcd();		//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(len==1 && b.len==1 && dats[0]==0 && b.dats[0]==0)
		return 0;
	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)
{
	bigint toreturn=*this;
	long long carry=0;
	unsigned i;
	toreturn.resize( ((b.len>toreturn.len)?b.len:toreturn.len) + 1 );

for(i=0; i<b.len; i++)
	{
		carry = (long long)toreturn.dats[i] + (long long)b.dats[i] + carry;
		toreturn.dats[i]=carry&(((long long)1<<32)-1);
		carry>>=32;
	}

for(; carry; i++)
	{
		carry=(long long)toreturn.dats[i] + carry;
		toreturn.dats[i]=carry&(((long long)1<<32)-1);
		carry>>=32;
	}

toreturn.resize();

return toreturn;
}

//1의 보수 사용
bigint bigint::sub(bigint &b)
{
	bigint toreturn(*this);
	bigint subtrahend(b);	//감수

unsigned len_new=((toreturn.len>b.len)?toreturn.len:b.len);
	subtrahend=subtrahend.negative(len_new);

toreturn=toreturn.add(subtrahend);
	if(toreturn.len > len_new)//자리올림수있으면
	{
		toreturn.resize(len_new);
		toreturn=toreturn.add((bigint)1);
	}
	else//자리올림수 없으면
	{
		toreturn=toreturn.negative(len_new);
		toreturn.sign=1;
	}
	return toreturn;
}

bigint bigint::mul(bigint &b)
{
	bigint result, tmp;
	unsigned i, j;
	unsigned 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=result.add(tmp);
		memset(tmp.dats, 0, sizeof(unsigned)*tmp.len);
	}
	result.resize();
	return result;	
}

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=r.sub(divisor);
		}
	}

if(ask_mod)
		return r;
	return q;
}

std::string bigint::conbcd()
{
	unsigned *bcd, len_new, head, i, j;
	char  str_tmp[10];
	std::string result;

len_new=10704*len/10000+1+len;

bcd=(unsigned*)calloc(len_new, sizeof(unsigned));
	memcpy(bcd, dats, sizeof(unsigned)*len);

for(head=len, i=0; i<32*len; i++)
	{
		for(j=head; j>=len; j--)
		{
			if(bcd[j]>=500000000)
				bcd[j]+=1647483648;
		}
		if(bcd[head]>>31)
			head++;
		bcd[head]<<=1;
		for(j=head-1; (int)j>=0; j--)
		{
			bcd[j+1]|=(bcd[j]>>31);
			bcd[j]<<=1;
		}		
	}

for(i=len_new-1; bcd[i]==0; i--);

sprintf(str_tmp, "%u", bcd[i]);
	result.insert(result.size(), str_tmp);

for(--i; i>=len; i--)
	{
		sprintf(str_tmp, "%09u", bcd[i]);
		result.insert(result.size(), str_tmp);
	}

free(bcd);
	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=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=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=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=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)
{
	*this=*this|b;
	return *this;
}

bigint bigint::operator&=(bigint b)
{
	*this=*this&b;
	return *this;
}
bigint bigint::operator^=(bigint b)
{
	*this=*this^b;
	return *this;
}

bigint bigint::operator+=(bigint b)
{
	*this=*this+b;
	return *this;
}

bigint bigint::operator-=(bigint b)
{
	*this=*this-b;
	return *this;
}

bigint bigint::operator*=(bigint b)
{
	*this=*this*b;
	return *this;
}

bigint bigint::operator/=(bigint b)
{
	*this=*this/b;
	return *this;
}

bigint bigint::operator%=(bigint b)
{
	*this=*this%b;
	return *this;
}

bigint bigint::operator<<=(bigint b)
{
	*this=*this<<b;
	return *this;
}

bigint bigint::operator>>=(bigint b)
{
	*this=*this>>b;
	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.conbcd();

return os;
}

std::istream& operator>>(std::istream& is, bigint& b)
{
	std::string numstr;
	is>>numstr;
	b=numstr.c_str();

return is;
}

bigint fac(bigint n)  
{  
	bigint result=1;
	for(; n>0; n--)
		result*=n;
	return result;
}

int main()
{
	std::ofstream fout;
	fout.open("result.txt");

bigint n=1;

std::cin>>n;
	while(n>0)
	{
		fout<<fac(n)<<'\n';
		std::cin>>n;
	}

return 0;
}

앜ㅋㅋㅋ 더럽다.

10진수 출력 고쳤어

이 글이 유익하다면 (굽신굽신) ->

Tag // bigint, C++, Class

Trackback(0) : Comment(4)

Trackback Address >> http://zfanta.com/trackback/459

　환타 2009/08/23 18:29 address modify / delete reply
논리적 오류가
　환타 2009/08/23 18:07 address modify / delete reply
많네
Dabin's 2009/08/29 11:13 address modify / delete reply
바보.
- address modify / delete 2009/08/29 19:48 　환타
  다고쳤어ㅋㅋ

visual studio 2008 설치

from 뻘소리 2008/08/20 13:43

우분투 포기후 윈도우를 다시 설치하고 첫 컴파일러

이제 C랑 MFC배우는 놈이 이 물건을 설치했다.

이쁜 거 뺴곤 뭐 다른 기능은 모르겠다 -ㅂ-
티타늄으로 파리채 만드는 격;

평가판다운로드

그것보다...

int main()
{
        while(1)
        {
                printf("개학이구나\n");
        }
        return 0;
}

이 글이 유익하다면 (굽신굽신) ->

Tag // c, C++, MFC, 개학, 숙제 어떡해, 컴파일러

Trackback(0) : Comment(10)

Trackback Address >> http://zfanta.com/trackback/401

브주듀 2008/08/20 21:44 address modify / delete reply
아놔. ㅋㅋ
진짜웃기네요.
왠지 모르게
int 놀기(){
while (!다 놀았다){
printf("아직이닷!!");
}
while(1){
놀기();
printf("개학이구나\n");
}

하고 싶네요..
- address modify / delete 2008/08/21 10:07 　환타
  개학은 참 무서워요 ㅜㅜ
알쯔 2008/08/20 23:18 address modify / delete reply
C 프로그램 개발할때는 vs2008보단 vs6.0 이 전 더 쉽고 낮더군요.
vs2008 너무 거대해요 ㅠ_ㅠ
- address modify / delete 2008/08/21 10:08 　환타
  vs6이 디버깅할 땐 좋더라구요 ㅎㅎ
  그래도 저는 여전히 공책으로 디버깅합니다 ㅋㅋ
마티오 2008/08/22 11:15 address modify / delete reply
비쥬얼 스튜디오라 하니.. 초등학교때 비쥬얼 베이직 만지작 거렸을때가 생각나는군요 ;ㅁ;...
- address modify / delete 2008/08/23 12:39 　환타
  비베는 한번도 안해본 언어 ㅋㅋㅋㅋ
  콘솔이 제일 편한 것 같아요 ㅋㅋ
Mr.번뜩맨 2008/08/22 21:43 address modify / delete reply
캬~ 언제봐도.. 신선하군요..
마지막 최민수의 썩소로 마무리..ㅋㅋ
- address modify / delete 2008/08/23 12:40 　환타
  개학시즌이라 곡소리가 많이 들려요 ㅜㅜ
Lonewolf dlbo 2008/08/23 01:16 address modify / delete reply
VS 2008이라.... 웹 개발 영역이 크게 확대되었고, 객체지향적인 프로그래밍에 크게 도움되도록 어시스트해주는 기능은 많지만 너무 무겁다는 단점이 있습니다. 단기간의 소형 프로그램을 만들때 제 경우는 VS 6.0으로, 중간규모나 그 이상이면 2005를 되도록 사용하고 있습니다. 2008은 비주얼 어시스트가 작동하질 않아서요 ㄱ-
- address modify / delete 2008/08/23 12:41 　환타
  vs 2008에서 사용하는 기능은 컨트롤 k+f 밖에 없네요 ;;; 어서 많이 배워야 할 텐데 ㅜㅜ

이 소스가 어떻게 컴파일이 되지.

from Programming/C/C++ 2008/03/13 17:33

옛날 소스파일을 보다 이런 걸 찾았다.

10번째 줄에서 int arr[a];가 있는데 별 일 없이 컴파일 된다.
실행에도 아무 문제 없다.

컴파일러는 dev-cpp, 다른 컴파일러

visual studio6,2005 는 컴파일이 안된다.
dev-cpp만 된다.
for문 10000번 VS 노가다 타이핑 10000번
예전에 이런 글을 쓴 적이 있는 데 좀 멍청했던 dev-cpp 공부좀 하셨나?

왜이렇게 어중간하게 구는겨.

이 글이 유익하다면 (굽신굽신) ->

Tag // c, C++, 컴파일러

Trackback(0) : Comment(7)

Trackback Address >> http://zfanta.com/trackback/363

러브네슬리 2008/03/13 23:43 address modify / delete reply
하하하~~저는 무슨말인지 하나도 모르겠다는;;
- address modify / delete 2008/03/15 14:09 　환타
  모르시는 게 속이 편하실겁니다. ㅋㅋ
  엄청 힘들어요 ㅜㅜ
Lonewolf dlbo 2008/03/15 13:36 address modify / delete reply
첫째로, system()이 VS시리즈에선 stdio.h 헤더파일로만 커버할 수 없습니다.
둘째로, 일반형 C언어라면 이 소스 자체의 구조가 컴파일에러입니다. 선언부가 실행명령 함수보다
아래에 위치해 있기 때문이지요. CPP이라면 상관없지만 C언어는 선언부는 반드시 함수 내 최상단에,
나머지 부분에 함수의 동작을 기술해야 합니다.
셋째로 동적할당의 유도를 위해 마이크로소프트가 VS에서 못 쓰게 막아둔 겁니다.
저렇게 사용할 경우 컴파일시 얼마나 용량을 할당하도록 결정하게 할 지 애매하게 되는데,
굳이 포인터라는 동적 할당을 두고 복잡하게 만들 필요가 없다는 판단때문에 VS에서는 막혀있는걸로 보입니다.
#pragma로 에러를 씹어버리고 컴파일하게 해도 VS에서는 컴파일이 안되는군요. 지금 VS6.0이 맛이 갔답니다 ㄱ-
- address modify / delete 2008/03/15 14:10 　환타
  컴파일러님께서 알아서 처리해주시는군요.
  저번 사건은 약간 미안해지는데요 ㅎㅎ
새벽태양 2008/03/16 20:04 address modify / delete reply
♣안녕하세요? 다음블로그 새벽태양 입니다. 오늘 좋은 내용을 잘 보고 갑니다.

오늘도 즐거운 하루 보내시고 행복하세요(www.21ds.gk.to 새벽태양)
Mastojun 2008/03/22 17:32 address modify / delete reply
C99에서는 배열을 상수가 아닌 변수로도 생성 가능합니다. dev-cpp는 이를 지원하는거구요. M$ 제품군은 아직은 프렌들리 비표준 입니다 :D
- address modify / delete 2008/03/22 22:25 　환타
  오.........