// arithmetic.cpp: определяет точку входа для консольного приложения.

// arithmetic.cpp: определяет точку входа для консольного приложения.

//

#include "stdafx.h"

#include <string.h>

typedef unsigned int uint32;

typedef long long unsigned int uint64;

typedef unsigned int uint;

const uint32 max_uint32(0-1);

const uint64 max_uint64(0-1);

const uint max_uint(0-1);

uint32 l(uint64 x){return (uint32)x;} //возрашяет младшую часть

uint32 h(uint64 x){return (uint32)(x>>32);} //возрашяет старшую часть

bool m_inc(uint32* data,uint size);

bool m_add(uint32* data,uint size, uint32 x);

uint32 m_mul(uint32* data,uint size, uint32 x);

uint32 m_div(uint32* data,uint size, uint32 x);

//добавление единицы к длинному числу с учётом переполнения

bool m_inc(uint32* data,uint size)

{

//прибавляю к первому числу

uint32* i= data;

(*i)+=1;

//пока есть переполнение прибовляю еденицу к следуещему числу

while (*i==0)

{

i++;

if (i==data+size) return true;

(*i)+=1;

}

return false;

}

//сложение длинного числа(массива чисел uint32 data) размера size(size >= 1) c числом x

bool m_add(uint32* data,uint size, uint32 x)

{

uint64 r =(uint64)x+(*data);

(*data) = l(r); //записываем младшую часть r в первое число в длинном числе

if (h(r)!=0) //если произошло переполнение

{

if (size>1) //проверяем есть ли следушие числа

return m_inc(data+1,size-1);

else

return true;

}

return false;

}

//умножение длинного числа(массива чисел uint32 data) размера size(size >= 1) c числом x

uint32 m_mul(uint32* data,uint size, uint32 x)

{

//алгоритм умножения столбиком (числа на цифру)

uint32* i= data;

uint64 r = (uint64)(*i)*x; //умножаем первое число длинного числа на x

*i = l(r); //записываем в первое число длинного числа младшую часть r

uint32 u= h(r); //запоминаем старшую часть

i++; //беру след. число длинного числа

while (i!=data+size)

{

//2^64 - 1 > (2^32-1)*(2^32-1)+(2^32-1)

//из этого следует что (uint64)(*i)*x + u поместиться в r и не возникнет переполнения....

r = (uint64)(*i)*x + u;

(*i)=l(r); //записываю младшию часть r в i-тое число длинного числа

u= h(r);

i++;

}

return u;

}

//size >=1

uint32 m_div(uint32* data,uint size, uint32 x)

{

uint32* i =(data+size-1);

uint64 r = *i;

*i=l(r/x);

r%=x;

i--;

while (i!=data-1)

{

r=r<<32;

r+=(*i);

*i=l(r/x);

r%=x;

i--;

}

return r;

}

//Класс для описания длинного числа

struct mlong_uint

{

////size >= 1

mlong_uint(uint size)

{

this->size=size;

this->data=new uint32[size];

}

mlong_uint(const mlong_uint& other)

{

size=other.size;

data=new uint32[size];

memcpy(data,other.data,size*sizeof(uint32));

}

//void swap(mlong_uint& other)

//{

// uint32 *m_data=data;

// uint m_size=size;

// size=other.size;

// data=other.data;

// other.size =m_size;

// other.data =m_data;

//}

mlong_uint& operator =(uint32 x)

{

set_to_zero();

data[0]=x;

return (*this);

}

mlong_uint& operator =(const mlong_uint& other)

{

delete[] data;

size=other.size;

data=new uint32[size];

memcpy(data,other.data,size*sizeof(uint32));

return (*this);

}

~mlong_uint()

{

delete[] data;

}

void set_to_zero()

{

memset(data,0,size*sizeof(uint32));

}

bool is_zero()const

{

for (uint32* i= data;i!=data+size;++i)

{

if ((*i)!=0) return false;

}

return true;

}

mlong_uint& operator ++()

{

m_inc(data,size);

return (*this);

}

mlong_uint& operator +=(uint32 x)

{

m_add(data,size,x);

return (*this);

}

mlong_uint& operator *=(uint32 x)

{

m_mul(data,size,x);

return (*this);

}

uint32 div_mod(uint32 x)

{

return m_div(data,size,x);

}

mlong_uint& operator /=(uint32 x)

{

div_mod(x);

return (*this);

}

uint32 operator%(uint32 x)const

{

mlong_uint t=(*this);

return t.div_mod(x);

}

uint32 get_digit(uint i) const

{

if (i<size)

return data[i];

else

return 0;

}

uint size;

uint32* data;

};

//--------------------------------------------------------------------

static char alph[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

const uint alph_len = 36;

uint32 getNum(char x)

{

return strchr(alph,x)-alph;

}

//base<=alph_len

void scan(mlong_uint &x,uint32 base=10)

{

char str[4096]="";

//ввод

char format_str[]="%4096s";

scanf(format_str, str);

//scanf("%c", str);

//преобразование строки в число

int i = 0;

if (str[i]!='\0')

{

x=getNum(str[i]);

i++;

while (str[i]!='\0')

{

x*=base;

x+=getNum(str[i]);

i++;

}

}

}

void print(const mlong_uint &x,uint32 base=10)

{

mlong_uint A=x;

//преобразование в строку

char str[4096+1];

int i = 4096;

str[i]='\0';

i--;

do

{

uint32 u = A.div_mod(base);

str[i]=alph[u];

i--;

}

while (!(A.is_zero()) && i!=-1);

//вывод

puts(str+i+1);

}

//--------------------------------------------------------------------

uint max(uint a,uint b)

{

if (a>b)

return a;

else

return b;

}

//сложение длинных чисел

mlong_uint m_add(const mlong_uint &data1,const mlong_uint &data2)

{

//------------------

//создаю пустое число для записи результата(мах возможного размера)

mlong_uint data_temp(max(data1.size,data2.size)+1);

//------------------

int i=0;

uint32 u = 0;

while (i<data_temp.size)

{

uint64 sum = (uint64)data1.get_digit(i) + data2.get_digit(i)+ u; // складываю числа

data_temp.data[i] = l(sum); //записываем младшую часть в первое число результата

u = h(sum);

i++;

}

return data_temp; //возрашяем результат сложения

}

int main()

{

mlong_uint k(2);

scan(k);

print(k);

mlong_uint k2(2);

scan(k2);

print(k2);

mlong_uint result_sum = m_add(k, k2); //сложить два длинных числа

//mlong_uint *result_sub = m_sub(k, k2); //отнять первое от второго

print(result_sum);

//print(result_sub);

return 0;

}

Дата добавления: 2015-11-04