计算器算法原理

计算器算法原理

除 法也用类似竖式的方法，从高位到低位逐一得出结果。大概过程如下：（注意，

是二进制 运算）

1

、先左移除数，直到除数不 小于被除数，同时记录移动的位数；

2

、开始循环，循环次数为前一步移动的位数加

1

；

3

、比较被除数与除数的大小，如果被除数不小 于除数，则该位结果为

1

，否则为

0< /p>

；

4

、除数右移一位，继续循环。

这种方法同样可以进行小数运算，根据需要的有效数字位数确定循环次数。

< br>

漏了一点，修改一下：

< /p>

3

、比较被除数与除数的大小，如果被除数不小于除数，则该位结 果为

1

，并把被除

数减去除数，否则为

0

加减乘除求余：

#include

#include

#include

#include

#define DEF_32

#ifdef DEF_32

typedef unsigned int uint;

const uint low_mask = 0xffff;

const uint hig_mask = 0xffff0000;

#else

typedef unsigned long long uint;

const uint low_mask = 0xffffffff;

const uint hig_mask = 0xffffffff00000000;

#endif

const uint alignment = 8;

struct _DATA_

...{

size_t capacity;//

容量

size_t len;//

使用的存储单元

uint *p;//

内容

};

typedef struct _DATA_ BigNumber;

typedef BigNumber* BigNumberPtr;

BigNumberPtr NewBigNumber(size_t len );

BigNumberPtr CopyNewBigNumber(BigNumberPtr p);

void CopyBigNumber(BigNumberPtr o,BigNumberPtr n);

BigNumberPtr ResizeBigNumber(BigNumberPtr p, size_t len );

void DestoryBigNumber(BigNumberPtr p);

void printBigNum( BigNumberPtr p );

void printBinBigNum( BigNumberPtr p );

int Borrow( uint* p , size_t len );//

借位

BigNumberPtr Carry(BigNumberPtr p);//

处理进位

BigNumberPtr RightShiftBigNumber(BigNumberPtr p, size_t pos );//

右移

BigNumberPtr LeftShiftBigNumber(BigNumberPtr p, size_t pos );//

左移

BigNumberPtr Multiply(BigNumberPtr ap,BigNumberPtr bp);//

乘法

BigNumberPtr Add(BigNumberPtr l,BigNumberPtr r);//

大数加法

BigNumberPtr AddNumber(BigNumberPtr l,uint n);//

加法

2

BigNumberPtr Sub(BigNumberPtr l,BigNumberPtr r);//

大数减法

BigNumberPtr SubThis(BigNumberPtr l,BigNumberPtr r);//

BigNumberPtr SubNumber(BigNumberPtr l,uint n);//

减法

BigNumberPtr DivideAndRemainder(BigNumberPtr l,BigNumberPtr r,BigNumberPtr

Remainder);//

除法< /p>

,

最后参数为余数

,

返回值为结果

size_t GetBitNum(uint n);

int main()

...{

int i=0;

const int test_len = 127;

BigNumberPtr l = NewBigNumber( test_len+1 );

BigNumberPtr r = NewBigNumber( test_len );

BigNumberPtr pRemainder =

NewBigNumber( test_len );

BigNumberPtr pRet = NULL;

srand( (unsigned int)time(NULL) );

for(i=0;i

l->p[i] = (rand()*rand())&low_mask;

r->p[i] = (rand()*rand())&low_mask;

}

l->p[i] = (rand()*rand())&low_mask;

printBigNum( l );

printBigNum( r );

pRet = DivideAndRemainder( l

, r , pRemainder);

if( pRet )...{

printf(

商

printf(

余数

DestoryBigNumber(pRet);

pRet = NULL;

}

DestoryBigNumber(pRemainder);

pRet = Multiply( l , r );

printf(

积

DestoryBigNumber(pRet);

pRet = NULL;

pRet = Sub( l , r );

if( pRet )...{

printf(

差

DestoryBigNumber(pRet);

pRet = NULL;

}

pRet = Add( l , r );

printf(

和

DestoryBigNumber(pRet);

pRet = NULL;

DestoryBigNumber(l);

DestoryBigNumber(r);

return 0;

}

BigNumberPtr NewBigNumber(size_t len )

...{

BigNumberPtr pRet = (BigNumberPtr)malloc( sizeof(BigNumber) );

pRet->len = len;

pRet->capacity = (len/alignment+1)*alignment;

pRet->p = (uint*)malloc( (size_t)(pRet->capacity*sizeof(uint)) );

memset( pRet->p , 0 , (size_t)(sizeof(uint)*(pRet->capacity) ) );

return pRet;

}

BigNumberPtr CopyNewBigNumber(BigNumberPtr p)

...{

BigNumberPtr pRet = (BigNumberPtr)malloc( sizeof(BigNumber) );

pRet->len = p->len;

pRet->capacity = p->capacity

pRet->p = (uint*)malloc( (size_t)(p->capacity*sizeof(uint)) );

memcpy( pRet->p , p->p , (size_t)(sizeof(uint)*pRet->capacity) );

return pRet;

}

BigNumberPtr ResizeBigNumber(BigNumberPtr p,size_t len )

...{

if( len > p->len )...{

if( p->capacity >=len )...{

memset( &(p->p[p->len]) , 0 ,(size_t)(sizeof(uint)*(p->capacity - p->len)) );

p->len = len

}else...{

BigNumberPtr pRet = NewBigNumber( len );

memcpy( pRet->p , p->p ,(size_t)(p->len*(sizeof(uint))) );

DestoryBigNumber( p );

return pRet;

}

}else if(len == p->len )

;

else

p->len = len

return p;

}

void CopyBigNumber(BigNumberPtr o,BigNumberPtr n)

...{

if( n->capacity >= o->len )...{

memcpy( n->p , o->p , (size_t)(o->len*sizeof(uint))

);

n->len = o->len;

}else...{

free( n->p );

n->p = (uint*)malloc( (size_t)(o->capacity*sizeof(uint))

n->capacity = o->capacity;

n->len = o->len;

memcpy( n->p , o->p , (size_t)(o->len*sizeof(uint))

);

}

}

void DestoryBigNumber(BigNumberPtr p)

...{

if( p )...{

if(p->p)

free( p->p );

free( p );

}

}

BigNumberPtr RemoveHigZero(BigNumberPtr p)

...{

while(0 == p->p[p->len-1])

p->len--;

if( 0 == p->len)

p->len=1;

return p;

}

BigNumberPtr Multiply(BigNumberPtr l,BigNumberPtr r)

...{

BigNumberPtr pRet = NewBigNumber( l->len + r->len );

BigNumberPtr pTemp = NewBigNumber( 1 + r->len );

uint i=0,j=0;

for( i=0 ilen i++)...{

for( j=0 jlen j++)

pTemp->p[j] = l->p[i]*r->p[j];

);

Carry( pTemp );

for( j=0 j< r->len+1 j++ )

pRet->p[i+j] += pTemp->p[j];

memset( pTemp->p , 0 , (size_t)(pTemp->len*sizeof(uint)) );

Carry( pRet );

}

DestoryBigNumber(pTemp);

return RemoveHigZero( pRet );

}

BigNumberPtr RightShiftBigNumber(BigNumberPtr p, size_t pos )

...{

size_t n = pos/(sizeof(uint)*4);

uint temp = 0

size_t j=0;

pos %= (sizeof(uint)*4);

if( n >0 )...{

p->len -= n

memcpy( p->p , p->p+n

, (size_t)(sizeof(uint)*(p->len)) );

}

if( 0 == pos )

return RemoveHigZero( p );

if( 1 == p->len )...{

p->p[0]>>=pos;

}else...{

for( j=0 j< p->len -1 j++)...{

temp = p->p[j+1] & low_mask

p->p[j] |= temp<<( sizeof(uint)*4 );

p->p[j]>>=pos;

p->p[j] &= low_mask;

}

p->p[j]>>=pos;

}

return RemoveHigZero( p );

}

BigNumberPtr LeftShiftBigNumber(BigNumberPtr p, size_t pos )

...{

const size_t n = pos/(sizeof(uint)*4);

const size_t org_len = p->len;

int temp = 0;

p = ResizeBigNumber( p , p->len + n + 1 );

pos %= (sizeof(uint)*4);

if( n > 0 )...{

for(temp=(int)org_len-1; temp>=0 temp-- )

p->p[temp+n] = p->p[temp];

memset( p->p , 0 , sizeof(uint)*n)

}

if( pos > 0 )...{

for(temp = 0

; temp < (int)p->len temp++ )

p->p[temp]<<=pos;

Carry( p );

}

return RemoveHigZero( p );

}

BigNumberPtr Add(BigNumberPtr l,BigNumberPtr r)

...{

BigNumberPtr pRet = NULL;

uint i=0;

size_t len=0;

if( l->len > r->len )

len = l->len;

else

len = r->len;

pRet = NewBigNumber( len + 1 );

for(i=0; i< len i ++)

pRet->p[i] = l->p[i] + r->p[i];

Carry( pRet );

return RemoveHigZero( pRet );

}

BigNumberPtr AddNumber(BigNumberPtr l,uint n)

...{

l->p[0] += n;

return Carry( l );

}

BigNumberPtr Sub(BigNumberPtr l,BigNumberPtr r)

...{

BigNumberPtr pRet = CopyNewBigNumber( l );

size_t i = 0;

for( i =0 i < pRet->len i++)...{

if( pRet->p[i] >= r->p[i] )

pRet->p[i] = pRet->p[i] - r->p[i];

else

if( Borrow( &(pRet->p[i]) , pRet->len-i ) )

pRet->p[i] = pRet->p[i] - r->p[i];

else...{

DestoryBigNumber( pRet );

return 0;

}

}