BigInteger를 구현해보자 - 3. 음수의 표현, 뺄셈

bigint에서 음수는 2의 보수 표기법을 사용하도록 한다. 그것이 덧셈 뺄셈에 간편하기 때문.
다음 함수는 2의 보수를 취해주는 함수이다. 즉 부호를 바꿔주는 함수.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

void bigint_neg(bigint *dest) {     for(u4 i=0;i<dest->len;++i)     {         dest->dats[i]=~dest->dats[i];     }     add_u4(dest->len, dest->dats,1); }   u4 bigint_createnegcopy(bigint *xi, const bigint *src) {     xi->len=src->len;     xi->dats=(u4*)malloc(xi->len*sizeof(u4));     if(xi->dats==NULL)return 0;     for(size_t i=0;i<xi->len;i++)     {         xi->dats[i]=~src->dats[i];     }     add_u4(xi->len, xi->dats, 1);     return xi->len; }

bigint_neg함수는 bigint의 부호를 바꿔주는 놈이고, createnegcopy는 부호가 반대인 놈을 복사해서 만들어주는 놈이다.
뺄셈은 2의보수를 취하고 더해주면 되지만, 그렇게 한다면 뺄셈을 할 때마다 2의보수를 취해야 하기 때문에 따로 구현하도록 한다.
자 다음 함수들을 먼저 만든다.

두 u4배열을 빼는 함수(받아내림 계산하고, 최상위자리에서 받아내림했을 경우 1을 리턴)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

inline u4 sub_a(u4 len,u4*dest,u4*src) {     u4 carry=1;     u4 temp;     for(u4 i=0;i<len;++i)     {         temp=~src[i];         dest[i]+=temp;         if(carry)         {             if(dest[i]>=temp)carry=0;             if(dest[i]==0xFFFFFFFF)carry=1;             ++dest[i];         }         else         {             if(dest[i]<temp)carry=1;         }     }     return carry; }

u4배열의 특정자리를 src만큼 빼주는 함수 (받아내림 계산하고, 최상위자리에서 받아내림했을 경우 1리턴)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

inline u4 sub_u4(u4 len, u4*dest, u4 src) {     u4 carry=0;     dest[0]-=src;     if(dest[0]>=src)carry=1;     for(u4 i=1;i<len;++i)     {         if(carry)         {             if(dest[i]!=0)carry=0;             --dest[i];         }         else         {             break;         }     }     return carry; }

자 이를 토대로 두 bigint를 빼는 함수를 만든다. 더하는 함수와 매우 유사하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void bigint_sub(bigint *dest, const bigint *src) {     if(dest->len<src->len)     {         sub_a(dest->len,dest->dats,src->dats);     }     else     {         if(sub_a(src->len,dest->dats,src->dats))         {             sub_u4(dest->len-src->len,&dest->dats[src->len],1);         }     } }

dest와 src의 길이를 비교해서 빼준다. dest와 src의 길이가 n이라면, 받아내림이 하나도 없을 경우 n회의 뺄셈을 하게되고, 최악의 경우 모든 자리에서 받아내림이 발생하면 2n회의 뺄셈을 하게되므로, 이 뺄셈 함수의 시간 복잡도는 덧셈과 마찬가지로 O(n)이 된다.