myutil.cpp

1024位的大整数进行相乘（N方）取模

#include "StdAfx.h"
#include ".\myutil.h"
#include <string.h> 
#include <stdlib.h>
#include<iostream>
#define MYUNION 1000000
#define MYUNION1 1048576
#define BINUNION 20
#define DECUNION 1000
#define DECBITS 3


using namespace std;

CMyUtil::CMyUtil(void)
{
}

CMyUtil::~CMyUtil(void)
{
}

void CMyUtil::DtoB(const char* decimal, char* binary)
{
	int * numArray=NULL;
	int d_length = strlen(decimal);
	int n_nums = d_length/6;
	int tail = d_length%6;
	if( tail )
		n_nums++;
	/*from int[0]  stores the lower bits, and int[n_nums-1] stores the  higher bits */
	numArray = new int[n_nums];

	this->getIntArray( decimal,numArray,n_nums,tail );

	

	int k=this->getBinArray(binary,numArray,n_nums);
	binary[k]=0;
	
	binary[ mm.length( binary) ]=0;
	mm.reverse( binary );
		
	delete numArray;
	numArray=NULL;
}


//notice : the binary array is in reverse order
int CMyUtil::getBinArray(char * binary,int* numArray,int n_nums)
{
	int k=0;
	int modTail;
	int flag;
	while( n_nums>0 ){
		flag=1;
		for( int i=n_nums-1;i>=1;i--){
			modTail = numArray[i]%1024;
			numArray[i]=numArray[i]/1024;
			numArray[i-1]+=modTail*MYUNION;
			if( numArray[i]==0 && flag==1 ){
				n_nums--;
			}else{
				flag=0;
			}
		}
		modTail = numArray[0]%1024;
		numArray[0]=numArray[0]/1024;
		for( int i=0;i<10;i++,k++ ){
			binary[k]='0'+modTail%2;
			modTail=modTail>>1;
		}
		if( numArray[0]==0 && flag==1 ){
			n_nums--;
		}else{
			flag=0;
		}
	}

	return k;
}

void CMyUtil::getIntArray(const char* decimal, int * numArray,int n_nums,int tail)
{
	
	char * numStr = new char[7];
	numStr[6]=0;
	if( tail ){
		for( int i=n_nums-1;i>=1;i-- ){
			for( int j=0; j<6;j++ ){
				numStr[j]=decimal[ tail+(i-1)*6+j];
			}
			numArray[n_nums-1-i]=atoi( numStr );
		}
	
		for( int j=0;j<tail;j++ ){
			numStr[j]=decimal[ j ];
		}
		numStr[tail]=0;
		numArray[n_nums-1]=atoi( numStr );
	}else{
		for( int i=n_nums-1;i>=0;i-- ){
			for( int j=0; j<6;j++ ){
				numStr[j]=decimal[ i*6+j ];
			}
			numArray[ n_nums-1-i]=atoi( numStr );
		
		}
	}
	

	delete numStr;
	numStr=NULL;
}



//notice: the decimal array is in reverse order
int CMyUtil::getDecArray(unsigned int * intArray , int n_nums, char* decimal)
{
	int k=0;
	int modTail;
	int flag;
	while( n_nums>0 ){
		flag=1;
		for( int i=n_nums-1;i>=1;i--){
			modTail = intArray[i]%DECUNION;
			intArray[i]=intArray[i]/DECUNION;
			intArray[i-1]+=modTail*MYUNION1;
			if( intArray[i]==0 && flag==1 ){
				n_nums--;
			}else{
				flag=0;
			}
		}
		modTail = intArray[0]%DECUNION;
		intArray[0]=intArray[0]/DECUNION;
		for( int i=0;i<3;i++,k++ ){
			decimal[k]='0'+modTail%10;
			modTail=modTail/10;
		}
		if( intArray[0]==0 && flag==1 ){
			n_nums--;
		}else{
			flag=0;
		}
	}

	return k;
}

void CMyUtil::BtoD(const char * binary , char * decimal)
{
	int b_length = strlen( binary );
	int n_nums = b_length/BINUNION;
	if( b_length%BINUNION )
		n_nums++;
	//the intArray[0] stores the lower part of the number
	if( n_nums==0 ){
		decimal[0]=0;	
		return;
	}
	unsigned int * intArray = new unsigned int[n_nums];
	this->getIntArrayFromB( intArray,binary,n_nums,b_length);

	int k=this->getDecArray(intArray,n_nums,decimal);
	decimal[k]=0;


	decimal[ mm.length( decimal) ]=0;
	mm.reverse( decimal );

	delete intArray;
	intArray=NULL;
}

void CMyUtil::getIntArrayFromB( unsigned int* intArray,const char * binary, int n_nums, int b_length)
{
	
	unsigned int temp;
	for( int i=0; i<n_nums-1;i++ ){
		int first_index=b_length-(i+1)*BINUNION;
		temp=binary[first_index]-'0';
		for( int j=1;j<BINUNION;j++ ){
			temp=temp<<1;
			if( binary[first_index+j]=='1' ){
				temp+=1;
			}
		}
		intArray[i]=temp;
	}


	int length=b_length-(n_nums-1)*BINUNION;
	temp=binary[0]-'0';
	for( int j=1;j<length;j++ ){
			temp=temp<<1;
			if( binary[j]=='1' ){
				temp+=1;
			}
	}
	intArray[n_nums-1]=temp;
	
	
}



void CMyUtil::HtoB(const char* hex, char* binary)
{
	int h_length = strlen( hex );
	int temp;
	int t;
	int first_index;
	for( int i=0;i<h_length;i++ ){
		if( hex[i]<='9' ){
			temp=hex[i]-'0';
		}else{
			t=hex[i];	
			if( t>='a'  )
				t-=32;
			temp=t-'A'+10;
		}
		first_index = 4*i;
		for( int j=3;j>=0;j-- ){
			binary[first_index+j]=temp%2+'0';
			temp=temp>>1;
		}
	}
	binary[  4* h_length ]=0;
	this->removeZero( binary );
}

void CMyUtil::BtoH(const char * binary , char * hex)
{
	int b_length=strlen( binary );
	if( b_length==0 ){
		hex[0]=0;
		return;
	}

	int h_length=( 3+b_length )/4;
	int first_length=b_length%4;
	if( first_length==0 )
		first_length=4;
	int temp;
	temp = binary[0]-'0';
	for( int i=1;i<first_length;i++ ){
		temp=temp<<1;
		if( binary[i]=='1' )
			temp+=1;
	}
	if( temp<=9 )
		hex[0]=temp+'0';
	else
		hex[0]=temp-10+'A';
	int first_index;
	for( int j=1;j<h_length;j++ ){
		first_index = first_length+(j-1)*4;
		temp = binary[first_index]-'0';
		for( int i=1;i<4;i++ ){
			temp=temp<<1;
			if( binary[first_index+i]=='1' )
				temp+=1;
		}
		if( temp<=9 )
			hex[j]=temp+'0';
		else
			hex[j]=temp-10+'A';
	}
	hex[h_length]=0;
}


void CMyUtil::removeZero( char * a)
{
	int a_length = strlen(a);
	int index=-1;
	int k=0;
	while( index<0&&k<a_length ){
		if( a[k]!='0' )
			index=k;
		k++;
	}
	if( index==0 )
		return;
	if( index>0 ){
		for( int i=index;i<a_length;i++ ){
			a[i-index]=a[i];
		}
		a[a_length-index]=0;
	}else{
		a[0]=0;
	}
}


void CMyUtil::OtoB(const char * oct , char * binary)
{
	int o_length = strlen( oct );
	int temp;
	int first_index;
	for( int i=0;i<o_length;i++ ){
		temp=oct[i]-'0';
		first_index = 3*i;
		for( int j=2;j>=0;j-- ){
			binary[first_index+j]=temp%2+'0';
			temp=temp>>1;
		}
	}
	binary[  3* o_length ]=0;
	this->removeZero( binary );
}

void CMyUtil::BtoO(const char* binary, char* oct)
{
	int b_length=strlen( binary );
	if( b_length==0 ){
		oct[0]=0;
		return;
	}

	int o_length=( 2+b_length )/3;
	int first_length=b_length%3;
	if( first_length==0 )
		first_length=3;
	int temp;
	temp = binary[0]-'0';
	for( int i=1;i<first_length;i++ ){
		temp=temp<<1;
		if( binary[i]=='1' )
			temp+=1;
	}
	oct[0]=temp+'0';

	int first_index;
	for( int j=1;j<o_length;j++ ){
		first_index = first_length+(j-1)*3;
		temp = binary[first_index]-'0';
		for( int i=1;i<3;i++ ){
			temp=temp<<1;
			if( binary[first_index+i]=='1' )
				temp+=1;
		}

	oct[j]=temp+'0';
		
	}
	oct[o_length]=0;
}