|
// 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; просмотров: 19 | Нарушение авторских прав
<== предыдущая лекция | | | следующая лекция ==> |
Текст читать (помним про транскрипцию!), переводить устно! | | | Army Camp - Армейский лагерь |