cpp1.cpp

大数运算,生成两个随机大数,然后计算他们的和,差等

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<memory.h>
#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);//除法,最后参数为余数,返回值为结果
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<test_len;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("商\n");printBigNum( pRet );
        printf("余数\n");printBigNum( pRemainder );
        DestoryBigNumber(pRet);
        pRet = NULL;
    }
    DestoryBigNumber(pRemainder);
    pRet = Multiply( l , r );
    printf("积\n");printBigNum( pRet );
    DestoryBigNumber(pRet);
    pRet = NULL;
    pRet = Sub( l , r );
    if( pRet ){
        printf("差\n");printBigNum( pRet );
        DestoryBigNumber(pRet);
        pRet = NULL;
    }
    pRet = Add( l , r );
    printf("和\n");printBigNum( pRet );
    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 ; i<l->len ; i++){
        for( j=0 ; j<r->len ; 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;
            }
    }
    Carry( pRet );
    return pRet;
}
BigNumberPtr SubThis(BigNumberPtr l,BigNumberPtr r)
{
    BigNumberPtr pRet = CopyNewBigNumber(l);
    uint 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;
            }
    }
    Carry( pRet );
    CopyBigNumber( pRet , l );
    DestoryBigNumber( pRet );
    return l;
}
int Borrow( uint* p , size_t len )
{
    if( 1 == len )
        return 0;
    if( p[1] > 0 ){
        p[1]--;
        p[0] += low_mask + 1;
        return 1;
    }else{
        if( Borrow( p+1 , len-1 ) ){
            p[1]--;
            p[0] += low_mask + 1;
            return 1;
        }
    }
    return 0;
}
BigNumberPtr SubNumber(BigNumberPtr l,uint n)
{
    if(l->p[0]>=n)
        l->p[0] -= n;
    else
        if( Borrow( l->p , l->len ) )
            l->p[0] -= n;
        else
            return 0;
    return l;
}
BigNumberPtr Carry(BigNumberPtr p)//处理进位
{
    size_t i;
    for(i=0;i<p->len-1; i ++){
        p->p[i+1] += (p->p[i]&hig_mask)>>(sizeof(uint)*4);
        p->p[i]&=low_mask;
    }
    if( p->p[i] > low_mask ){
        p = ResizeBigNumber( p , p->len + 1 );
        p->p[i+1] += (p->p[i]&hig_mask)>>(sizeof(uint)*4);
        p->p[i]&=low_mask;
    }
    return p;
}
size_t GetBitNum(uint n)
{
    int i=0;
    const uint temp = 1;
    uint t;
    for( i = sizeof(uint)*4 ; i >=0 ; i-- ){
        t= temp<<i;
        if( n&t )
            break;
    }
    return i;
}
BigNumberPtr DivideAndRemainder(BigNumberPtr l,BigNumberPtr r,BigNumberPtr
                                Remainder)
{
    BigNumberPtr pRet = CopyNewBigNumber( l );
    BigNumberPtr pTemp = CopyNewBigNumber( r );
    BigNumberPtr p = NULL;
    BigNumberPtr pResult = NewBigNumber( 1 );
    size_t n = GetBitNum( pRet->p[pRet->len-1] ) + (size_t)(sizeof(uint)*4*(pRet->len-1)) ;
    const size_t n2 = GetBitNum( r->p[r->len-1] ) + (size_t)(sizeof(uint)*4*(r->len-1)) ;
    size_t i=0;
    pTemp = LeftShiftBigNumber( pTemp , n-n2 );
    for( i=0 ; i<n-n2;i++){
        p = SubThis( pRet , pTemp );
        if( p )
            AddNumber( pResult , 1 );
        pResult = LeftShiftBigNumber( pResult , 1 );
        pTemp = RightShiftBigNumber( pTemp , 1 );
    }
    p = SubThis( pRet , pTemp );
    if( p )
        AddNumber( pResult , 1 );
    if( Remainder )
        CopyBigNumber( pRet , Remainder );
    DestoryBigNumber( pRet );
    DestoryBigNumber( pTemp );
    RemoveHigZero( Remainder );
    return pResult;
};
void printBigNum( BigNumberPtr p )
{
    size_t i=0;
    for( i=0 ; i<p->len ; i++ ){
#ifdef DEF_32
        printf("%04X",p->p[ p->len-i-1 ] );
#else
        printf("%08X",p->p[ p->len-i-1 ] );
#endif
    }
    printf("\n");
}
void printBinBigNum( BigNumberPtr p )
{
    uint i=0,j=0;
    const uint k=1;
    for( i=0 ; i<p->len ; i++ ){
        printf("\n%08X   " ,p->p[p->len-i-1] );
        for( j=0;j<sizeof(uint)*4 ; j++ ){
            printf("%c" , (p->p[p->len-i-1]&(k<<(sizeof(uint)*4-j-1)) )?'1':'0' );
            if( 7==j%8 )printf(" ");
        }
    }
    printf("\n");
}