Оптимизация — оптимизация кода на C ++ для добавления двух чисел, взятых в виде строки
Я работал над функцией, которая читает две строки, имеющие цифры, и выводит сумму двух. Например, если я передаю «100» и «99» через свою функцию, выводится «199». Я делаю это, чтобы иметь дело с числами, скажем, длиной в 100 цифр. Многие реализации, использующие перегрузку операторов и классы, существуют в Интернете для обработки таких больших целых чисел, но я не хочу, чтобы такой сложный код был таким сложным. Я просто хочу написать базовые операции +, -, /, * и%. Я записал следующий код для добавления. Но я чувствую, что должен оптимизировать это дальше. Любые советы по оптимизации приведенного ниже кода и как оптимизировать применение операторов умножения, деления и%?
char* Add(char *s1,char *s2)
{
char *A,*B;
int L1=strlen(s1),L2=strlen(s2),La,Lb,i;
if(L1>=L2)
{
A=s1; La=L1;
B=s2; Lb=L2;
}
else
{
A=s2; La=L2;
B=s1; Lb=L1;
}
int L=La+2;
char s[L];
s[L-1]='\0';
s[0]='0'; int temp=0;
for(i=0;i<Lb;i++)
{
int x=((int)(A[La-1-i]-'0')+(int)(B[Lb-1-i]-'0'));
s[L-2-i]=(char)((x+temp)%10+'0');
temp=x/10;
}
for(i=La-Lb-1;i>=0;i--)
{
int x=(int)(A[i]-'0');
s[L-La+i-1]=(char)((x+temp)%10+'0');
temp=x/10;
}
s[0]=(char)(temp+'0');
char *sum = s[0]!='0' ? &s[0] : &s[1];
return sum;
}
Проблемы:
Когда в основной функции я пишу что-то вроде
char *c=(char*)Add("99","10");
c=(char*)Add(c,"10");
std::cout<<c;
Он печатает ненужные значения.
Когда в основной функции я пишу что-то вроде:
char *c=(char*) Add("999999999999999999999999999","10000");
std::cout<<c;
Я получаю ненужные значения, хотя печать «сумма» в самой функции дает правильный вывод.
Некоторые моменты о моей программе:
- A длиннее двух строк s1 и s2, а B короче двух.
- La — это длина A, а Lb — это длина B.
- s — строка, хранящая конечный результат с длиной L = (La + 1) +1, потому что вывод может быть не более чем на 1 цифру длиннее, чем A.
- сумма указывает на первый символ s [1], если результат равен A и s [0], если результат на один символ длиннее A.
Пример:
Если A = 100 B = 99, то s = 0199 и, следовательно, сумма указывает на s [1].
Если A = 99, B = 99, то s = 198 и, следовательно, сумма указывает на s [0].
Решение
Я согласен с комментарием «использовать std::string«- в целом, накладные расходы не намного больше, чем при использовании ручного распределения с malloc(L) или же new char[L]и имеет то преимущество, что позволяет вам «запускать и забывать» сложные выражения, такие как:
std::string a = "102";
std::string b = "192312";
std::string c = Add(a, Add(b, Add(a, Add(b, a))));
Очевидно, я предполагаю, что вы захотите сделать общую математику, а не просто добавить, и в этом случае вышеупомянутое имеет больше смысла, например. c = Add(a, Mul(a, b)) сделал бы c = a + a * b;
Если вы выполняете описанные выше сложные вызовы с использованием ручного выделения, вам придется сохранить все промежуточные значения, а затем освободить их, когда они больше не нужны, например:
этот:
std::string c = Add(a, Add(b, Add(a, Add(b, a))));
будет выглядеть так:
char *tmp1 = Add(b, a);
char *tmp2 = Add(a, tmp1);
delete [] tmp1; // Assuming we use `new`, otherwise `free tmp1` if using `malloc`.
char *tmp3 = Add(b, tmp2);
delete [] tmp2;
char *c = Add(a, tmp3);
... do stuff with c
delete [] c;
std::string также отслеживает фактическую длину, что означает strlen больше не «дорогой» — std::string::length() очень простая функция со сложностью O (1) — где strlen() равно O (n) — то есть время, которое оно занимает, пропорционально длине строки.
Другие решения
Исходя из того, что вы написали, я думаю, проблема в том, что sum размещается в стеке. Как таковой, он гарантированно будет действителен только в течение срока его действия Add функция). Вместо этого вы должны выделить новый буфер символов в куче и вернуть его. Например.,
char* s = new char[L];
Редактировать: Как уже отмечали другие, вы можете рассмотреть возможность использования строки вместо символьного массива. Они немного дружелюбнее.
Тем не менее, если вы не хотите использовать строку, учитывая ваш код, приведенное выше решение может привести к утечке памяти (первый символ, если s начинается с ‘0’). Вместо этого вы можете использовать исходный код, изменив конец следующим образом.
char* sum;
if (s[0] == '0')
{
sum = new char[strlen(s)];
strcpy(sum,s+1);
}
else
{
sum = new char[strlen(s) + 1];
strcpy(sum,s);
}
Опять же, большая проблема заключается в том, что s а также sum являются локальными для вашей функции. Это означает, что после выполнения вашей функции среда выполнения может свободно использовать их память. Чем пользуетесь new позволяет вам выделить память для «кучи», которая не будет перезаписана средой выполнения, пока вы не освободите связанную память. Воткраткое руководство, объясняющее основную идею.
Редактировать 2: Как указывал ниже комментатор, ошибка может быть причиной переполнения. Я отредактировал код выше, чтобы избавиться от проблемы. Тем не менее, это хороший пример того, почему лучше использовать std::string на первом месте.
Чтобы дать предложения по улучшению (другая половина вашего вопроса), тогда я бы предложил прекратить делать так много ненужных вычислений. Как например
for(i=0;i<Lb;i++)
{
int x=((int)(A[La-1-i]-'0')+(int)(B[Lb-1-i]-'0'));
s[L-2-i]=(char)((x+temp)%10+'0');
temp=x/10;
}
лучше можно записать как:
int ib,ia,is;
for (
int ib = Lb-1, int ia = La-1, int is = L-1;
ib >= 0;
ib--, ia--, is--
) {
int x=((int)(A[ib]-'0')+(int)(B[ib]-'0'));
s[is]=(char)((x+temp)%10+'0');
temp=x/10;
}
который спасет вас всех тех La-1-i расчеты каждый проход через цикл, и они также делают код более четким (IMHO).
Другой момент — отбросить (int) и (char) приведений; они не нужны.
Третий пункт — не использовать деление и модуль, если вы можете помочь — это потенциально относительно длительные операции. В этом цикле вы знаете, что добавление 2 цифр может быть не более 18, поэтому x/10 слишком сложный, и может быть заменен простой структурой, подобной if temp = x>9? x-10: x, То же самое касается%.
Более продуманное решение, которое вы могли бы принять, касается постоянного преобразования между текстовым и числовым представлением цифр. Если ваши big-int-строки тратят больше времени на вычисления, чем на ввод / вывод, то может быть целесообразно предварительно и пост преобразовать их только один раз. Таким образом, текстовая строка сначала отображается в своей числовой форме (каждый символ — = ‘0’), затем с помощью этой формы вы делаете все свои вычисления, и только перед тем, как вы снова ее выводите, вы снова делаете все цифры текстовыми (каждый символ + = ‘ 0’ ).
И еще одна (микро) оптимизация: не используйте post-fix — когда пре-исправная версия будет работать так же, используйте здесь —ia вместо ia—. x— имеет некоторые издержки, потому что он возвращает значение x до того, как оно уменьшилось, что приводит к int temp = x, --x, return temp,
Я считаю, что если вы хотите правильно реализовать операторы деления и по модулю, то вам следует хранить число как «необработанные данные» вместо формата ASCII (иными словами, представлять его в базе данных-2 вместо базы-10).
Ниже моя реализация для класса, который хранит натуральное число любого возможного размера. Он поддерживает любую арифметическую операцию, предоставляемую C ++, и предоставляет интерфейс для преобразования числа в / из строки ASCII на любом основании (до base-36, так как после этого больше нет цифр и букв).
Число поддерживается как little-endian, но код совместим с обоими типами архитектур.
Вот как вы можете использовать его для реализации ваших char* Add(char *s1,char *s2) функция:
NaturalNum n1 = StringToNaturalNum(s1,10);
NaturalNum n2 = StringToNaturalNum(s2,10);
NaturalNum sum = n1+n2;
int s1len = strlen(s1);
int s2len = strlen(s2);
char* str = new char[MAX(s1len,s2len)+2];
sum.ToString(str,10);
return str;
А вот и реализация NaturalNum сам класс:
Файл NaturalNum.h:
#ifndef NATURAL_NUM_H
#define NATURAL_NUM_Hclass NaturalNum
{
public: //Constructors + Destructor
NaturalNum();
virtual ~NaturalNum();
NaturalNum(unsigned int iNaturalNum);
NaturalNum(const NaturalNum& cNaturalNum);
//---------------------------------------------------------------------------------------------
public: //Assignment Operators
virtual const NaturalNum& operator=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator+=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator-=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator*=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator/=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator%=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator|=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator&=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator^=(const NaturalNum& cNaturalNum);
virtual const NaturalNum& operator<<=(unsigned int iShift);
virtual const NaturalNum& operator>>=(unsigned int iShift);
//---------------------------------------------------------------------------------------------
public: //Unary Operators
virtual NaturalNum operator~() const;
virtual const NaturalNum& operator++();
virtual const NaturalNum& operator--();
virtual NaturalNum operator++(int dummy);
virtual NaturalNum operator--(int dummy);
//---------------------------------------------------------------------------------------------
public: //Binary Operators
friend NaturalNum operator+(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator-(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator*(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator/(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator%(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator|(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator&(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend NaturalNum operator^(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
virtual NaturalNum operator<<(unsigned int iShift) const;
virtual NaturalNum operator>>(unsigned int iShift) const;
//---------------------------------------------------------------------------------------------
public: //Binary Comperators
friend bool operator<(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend bool operator>(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend bool operator==(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend bool operator<=(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend bool operator>=(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
friend bool operator!=(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2);
//---------------------------------------------------------------------------------------------
public: //Interface Routines
unsigned int BitCount() const;
void ToBuffer(unsigned char aBuffer[]) const;
void ToString(char aString[],unsigned int iBase) const;
friend NaturalNum StringToNaturalNum(const char aString[],unsigned int iBase);
//---------------------------------------------------------------------------------------------
protected: //Internal Routines
void Allocate(unsigned int iBytes);
void DeallocateAll();
void RemoveRedundantZeros();
//---------------------------------------------------------------------------------------------
protected: //Object Attributes
unsigned int m_iLength;
unsigned char* m_aValues;
//---------------------------------------------------------------------------------------------
};#endif
Файл NaturalNum.cpp:
#include "NaturalNum.h"
///////////////////////////////////////
// Constructors + Destructor (below) //NaturalNum::NaturalNum()
{
Allocate(0);
}NaturalNum::~NaturalNum()
{
DeallocateAll();
}NaturalNum::NaturalNum(unsigned int iNaturalNum)
{
Allocate(sizeof(iNaturalNum));
for (unsigned int i=0; i<m_iLength; i++)
m_aValues[i]=iNaturalNum>>(i*8);
RemoveRedundantZeros();
}NaturalNum::NaturalNum(const NaturalNum& cNaturalNum)
{
Allocate(0);
*this=cNaturalNum;
}// Constructors + Destructor (above) //
/////////////////////////////////////////////////////////////////////////
// Assignment Operators (below) //const NaturalNum& NaturalNum::operator=(const NaturalNum& cNaturalNum)
{
if (this==&cNaturalNum)
return *this;
DeallocateAll();
Allocate(cNaturalNum.m_iLength);
for (unsigned int i=0; i<m_iLength; i++)
m_aValues[i]=cNaturalNum.m_aValues[i];
return *this;
}const NaturalNum& NaturalNum::operator+=(const NaturalNum& cNaturalNum)
{
return *this=*this+cNaturalNum;
}const NaturalNum& NaturalNum::operator-=(const NaturalNum& cNaturalNum)
{
return *this=*this-cNaturalNum;
}const NaturalNum& NaturalNum::operator*=(const NaturalNum& cNaturalNum)
{
return *this=*this*cNaturalNum;
}const NaturalNum& NaturalNum::operator/=(const NaturalNum& cNaturalNum)
{
return *this=*this/cNaturalNum;
}const NaturalNum& NaturalNum::operator%=(const NaturalNum& cNaturalNum)
{
return *this=*this%cNaturalNum;
}const NaturalNum& NaturalNum::operator|=(const NaturalNum& cNaturalNum)
{
return *this=*this|cNaturalNum;
}const NaturalNum& NaturalNum::operator&=(const NaturalNum& cNaturalNum)
{
return *this=*this&cNaturalNum;
}const NaturalNum& NaturalNum::operator^=(const NaturalNum& cNaturalNum)
{
return *this=*this^cNaturalNum;
}const NaturalNum& NaturalNum::operator<<=(unsigned int iShift)
{
return *this=*this<<iShift;
}const NaturalNum& NaturalNum::operator>>=(unsigned int iShift)
{
return *this=*this>>iShift;
}// Assignment Operators (above) //
///////////////////////////////////////////////////////////////
// Unary Operators (below) //NaturalNum NaturalNum::operator~() const
{
NaturalNum cRes;
cRes.Allocate(m_iLength);
for (unsigned int i=0; i<m_iLength; i++)
cRes.m_aValues[i]=~m_aValues[i];
return cRes;
}const NaturalNum& NaturalNum::operator++()
{
*this+=1;
return *this;
}const NaturalNum& NaturalNum::operator--()
{
*this-=1;
return *this;
}NaturalNum NaturalNum::operator++(int dummy)
{
NaturalNum cRes=*this;
*this+=1;
return cRes;
}NaturalNum NaturalNum::operator--(int dummy)
{
NaturalNum cRes=*this;
*this-=1;
return cRes;
}// Unary Operators (above) //
///////////////////////////////////////////////////////////
// Binary Operators (below) //NaturalNum operator+(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum2.m_iLength<cNaturalNum1.m_iLength)
return cNaturalNum2+cNaturalNum1;
NaturalNum cRes;
cRes.Allocate(cNaturalNum2.m_iLength+1);
unsigned int i;
unsigned short iSum;
unsigned char iRem=0;
for (i=0; i<cNaturalNum1.m_iLength; i++)
{
iSum=iRem+cNaturalNum1.m_aValues[i]+cNaturalNum2.m_aValues[i];
cRes.m_aValues[i]=iSum&0xFF;
iRem=iSum>>8;
}
for (; i<cNaturalNum2.m_iLength; i++)
{
iSum=iRem+cNaturalNum2.m_aValues[i];
cRes.m_aValues[i]=iSum&0xFF;
iRem=iSum>>8;
}
cRes.m_aValues[i]=iRem;
cRes.RemoveRedundantZeros();
return cRes;
}NaturalNum operator-(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum2>cNaturalNum1)
throw "Negative Result";
NaturalNum cRes;
cRes.Allocate(cNaturalNum1.m_iLength);
unsigned int i;
signed short iDif;
signed char iRem=0;
for (i=0; i<cNaturalNum2.m_iLength; i++)
{
iDif=iRem+cNaturalNum1.m_aValues[i]-cNaturalNum2.m_aValues[i];
cRes.m_aValues[i]=iDif&0xFF;
iRem=iDif>>8;
}
for (; i<cNaturalNum1.m_iLength; i++)
{
iDif=iRem+cNaturalNum1.m_aValues[i];
cRes.m_aValues[i]=iDif&0xFF;
iRem=iDif>>8;
}
cRes.RemoveRedundantZeros();
return cRes;
}NaturalNum operator*(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
NaturalNum cRes=0;
for (unsigned int i=0; i<cNaturalNum1.m_iLength; i++)
for (unsigned int j=0; j<cNaturalNum2.m_iLength; j++)
cRes+=(NaturalNum)(cNaturalNum1.m_aValues[i]*cNaturalNum2.m_aValues[j])<<((i+j)*8);
return cRes;
}NaturalNum operator/(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum2==0)
throw "Infinite Result";
NaturalNum cRes=0;
NaturalNum cTmp1=cNaturalNum1;
unsigned int iTmp1Len=cTmp1.BitCount();
unsigned int iNaturalNum2Len=cNaturalNum2.BitCount();
while (iTmp1Len>iNaturalNum2Len)
{
cRes+=(NaturalNum)1<<(iTmp1Len-iNaturalNum2Len-1);
cTmp1-=cNaturalNum2<<(iTmp1Len-iNaturalNum2Len-1);
iTmp1Len=cTmp1.BitCount();
}
if (cTmp1>=cNaturalNum2)
return cRes+1;
return cRes;
}NaturalNum operator%(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
return cNaturalNum1-cNaturalNum1/cNaturalNum2*cNaturalNum2;
}NaturalNum operator|(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum2.m_iLength<cNaturalNum1.m_iLength)
return cNaturalNum2|cNaturalNum1;
NaturalNum cRes;
cRes.Allocate(cNaturalNum2.m_iLength);
unsigned int i;
for (i=0; i<cNaturalNum1.m_iLength; i++)
cRes.m_aValues[i]=cNaturalNum1.m_aValues[i]|cNaturalNum2.m_aValues[i];
for (; i<cNaturalNum2.m_iLength; i++)
cRes.m_aValues[i]=0|cNaturalNum2.m_aValues[i];
cRes.RemoveRedundantZeros();
return cRes;
}NaturalNum operator&(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum2.m_iLength<cNaturalNum1.m_iLength)
return cNaturalNum2&cNaturalNum1;
NaturalNum cRes;
cRes.Allocate(cNaturalNum2.m_iLength);
unsigned int i;
for (i=0; i<cNaturalNum1.m_iLength; i++)
cRes.m_aValues[i]=cNaturalNum1.m_aValues[i]&cNaturalNum2.m_aValues[i];
for (; i<cNaturalNum2.m_iLength; i++)
cRes.m_aValues[i]=0&cNaturalNum2.m_aValues[i];
cRes.RemoveRedundantZeros();
return cRes;
}NaturalNum operator^(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum2.m_iLength<cNaturalNum1.m_iLength)
return cNaturalNum2^cNaturalNum1;
NaturalNum cRes;
cRes.Allocate(cNaturalNum2.m_iLength);
unsigned int i;
for (i=0; i<cNaturalNum1.m_iLength; i++)
cRes.m_aValues[i]=cNaturalNum1.m_aValues[i]^cNaturalNum2.m_aValues[i];
for (; i<cNaturalNum2.m_iLength; i++)
cRes.m_aValues[i]=0^cNaturalNum2.m_aValues[i];
cRes.RemoveRedundantZeros();
return cRes;
}NaturalNum NaturalNum::operator<<(unsigned int iShift) const
{
unsigned int iByteShift=iShift/8;
unsigned int iBitsShift=iShift%8;
if (m_iLength==0)
return 0;
NaturalNum cRes;
cRes.Allocate(m_iLength+iByteShift+1);
for (unsigned int n=0; n<iByteShift; n++)
cRes.m_aValues[n]=0;
unsigned int i;
unsigned char iRem=0;
for (i=iByteShift; i<m_iLength+iByteShift; i++)
{
cRes.m_aValues[i]=(m_aValues[i-iByteShift]<<iBitsShift)|iRem;
iRem=m_aValues[i-iByteShift]>>(8-iBitsShift);
}
cRes.m_aValues[i]=iRem;
cRes.RemoveRedundantZeros();
return cRes;
}NaturalNum NaturalNum::operator>>(unsigned int iShift) const
{
unsigned int iByteShift=iShift/8;
unsigned int iBitsShift=iShift%8;
if (m_iLength<=iByteShift)
return 0;
NaturalNum cRes;
cRes.Allocate(m_iLength-iByteShift);
unsigned int i;
unsigned char iRem;
for (i=0; i<m_iLength-iByteShift-1; i++)
{
iRem=m_aValues[i+iByteShift+1]<<(8-iBitsShift);
cRes.m_aValues[i]=(m_aValues[i+iByteShift]>>iBitsShift)|iRem;
}
iRem=m_aValues[i+iByteShift]>>iBitsShift;
cRes.m_aValues[i]=iRem;
cRes.RemoveRedundantZeros();
return cRes;
}// Binary Operators (above) //
//////////////////////////////////////////////////////////////
// Binary Comperators (below) //bool operator<(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum1.m_iLength!=cNaturalNum2.m_iLength)
return cNaturalNum1.m_iLength<cNaturalNum2.m_iLength;
for (unsigned int i=cNaturalNum1.m_iLength; i>0; i--)
if (cNaturalNum1.m_aValues[i-1]!=cNaturalNum2.m_aValues[i-1])
return cNaturalNum1.m_aValues[i-1]<cNaturalNum2.m_aValues[i-1];
return false;
}bool operator>(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum1.m_iLength!=cNaturalNum2.m_iLength)
return cNaturalNum1.m_iLength>cNaturalNum2.m_iLength;
for (unsigned int i=cNaturalNum1.m_iLength; i>0; i--)
if (cNaturalNum1.m_aValues[i-1]!=cNaturalNum2.m_aValues[i-1])
return cNaturalNum1.m_aValues[i-1]>cNaturalNum2.m_aValues[i-1];
return false;
}bool operator==(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
if (cNaturalNum1.m_iLength!=cNaturalNum2.m_iLength)
return false;
for (unsigned int i=cNaturalNum1.m_iLength; i>0; i--)
if (cNaturalNum1.m_aValues[i-1]!=cNaturalNum2.m_aValues[i-1])
return false;
return true;
}bool operator<=(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
return !(cNaturalNum1>cNaturalNum2);
}bool operator>=(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
return !(cNaturalNum1<cNaturalNum2);
}bool operator!=(const NaturalNum& cNaturalNum1,const NaturalNum& cNaturalNum2)
{
return !(cNaturalNum1==cNaturalNum2);
}// Binary Comperators (above) //
////////////////////////////////////////////////////////////////
// Interface Routines (below) //unsigned int NaturalNum::BitCount() const
{
if (m_iLength==0)
return 0;
unsigned int iBitCount=(m_iLength-1)*8;
for (unsigned int i=1; i<=m_aValues[m_iLength-1]; i<<=1)
iBitCount++;
return iBitCount;
}void NaturalNum::ToBuffer(unsigned char aBuffer[]) const
{
for (unsigned int i=0; i<m_iLength; i++)
aBuffer[i]=m_aValues[i];
}void NaturalNum::ToString(char aString[],unsigned int iBase) const
{
unsigned int iIndex=0;
for (NaturalNum cTmp=*this; cTmp>0; cTmp/=iBase)
{
NaturalNum cDigit=cTmp%iBase;
if (cDigit==0)
aString[iIndex]='0';
else if (cDigit<10)
aString[iIndex]='0'+cDigit.m_aValues[0];
else
aString[iIndex]='A'+cDigit.m_aValues[0]-10;
iIndex++;
}
for (unsigned int i=0; i<iIndex/2; i++)
{
char iDigit=aString[i];
aString[i]=aString[iIndex-1-i];
aString[iIndex-1-i]=iDigit;
}
if (iIndex==0)
aString[iIndex++]='0';
aString[iIndex]=0;
}NaturalNum StringToNaturalNum(const char aString[],unsigned int iBase)
{
NaturalNum cRes=0;
for (unsigned int i=0; aString[i]!=0; i++)
{
NaturalNum cDigit;
if ('0'<=aString[i] && aString[i]<='9')
cDigit=aString[i]-'0';
else if ('A'<=aString[i] && aString[i]<='Z')
cDigit=aString[i]-'A'+10;
else if ('a'<=aString[i] && aString[i]<='z')
cDigit=aString[i]-'a'+10;
else
break;
cRes*=iBase;
cRes+=cDigit;
}
return cRes;
}// Interface Routines (above) //
///////////////////////////////////////////////////////////////
// Internal Routines (below) //void NaturalNum::Allocate(unsigned int iBytes)
{
m_iLength=iBytes;
if (m_iLength>0)
m_aValues=new unsigned char[m_iLength];
}void NaturalNum::DeallocateAll()
{
if (m_iLength>0)
delete[] m_aValues;
m_iLength=0;
}void NaturalNum::RemoveRedundantZeros()
{
while (m_iLength>0 && m_aValues[m_iLength-1]==0)
if (--m_iLength==0)
delete[] m_aValues;
}// Internal Routines (above) //
///////////////////////////////
detector