华为"128为大整数相加"机试题

最近正直春招,偶尔接触到了华为的这道大整数相加的测试题,在网上找了一个算法,然后自己尝试进行了优化,最后也对memmove()函数效率有了进一步把握.

#include <time.h>
#include <iostream>
using namespace std;

#define MAX_LENGTH 128

void Add(const char *pszOperand1, const char *pszOperand2, char *pszResult); //互联网上原始代码
void Add2(const char *pszOperand1, const char *pszOperand2, char *pszResult, size_t len ); //优化后的代码

int main()
{
char szOperand1[MAX_LENGTH + 1], szOperand2[MAX_LENGTH + 1], szResult[MAX_LENGTH + 2];

cin >> szOperand1 >> szOperand2;

clock_t startTime = clock();
for ( int i = 0; i < 100000000; ++i ) //原始代码测试
{
Add(szOperand1, szOperand2, szResult);
}
clock_t endTime = clock();
cout << szOperand1 << " + " << szOperand2 << " = " << szResult << endl;
cout << "Total time = " << endTime - startTime << endl; //132725ms

startTime = clock();
for ( int i = 0; i < 100000000; ++i ) //优化后代码测试
{
Add2( szOperand1, szOperand2, szResult, MAX_LENGTH+2 );
}
endTime = clock();

cout << szOperand1 << " + " << szOperand2 << " = " << szResult << endl;
cout << "Total time = " << endTime - startTime << endl; //84287ms

//总结：Add2()函数比Add()函数在使用了memmove()优化后效率提升了36.28%，而空间节省了40%。
return 0;
}

void Add(const char *pszOperand1, const char *pszOperand2, char *pszResult)
{
short iResult[MAX_LENGTH + 1];
short iCarry = 0;

int i = (int) strlen(pszOperand1) - 1;
int j = (int) strlen(pszOperand2) - 1;
int k = MAX_LENGTH + 1;

while (i >= 0 || j >= 0)
{
  k--;
  iResult[k] = 0;
  if (i >= 0)
   iResult[k] += pszOperand1[i--] - '0';
  if (j >= 0)
   iResult[k] += pszOperand2[j--] - '0';
  iResult[k] += iCarry;

  if (iResult[k] >= 10)
  {
   iResult[k] -= 10;
   iCarry = 1;
  }
  else
   iCarry = 0;
}

if (iCarry == 1)
iResult[--k] = 1;

i = 0;
for (; k <= MAX_LENGTH; k++, i++)
pszResult[i] = iResult[k] + '0';
pszResult[i] = '';
}

void Add2(const char *pszOperand1, const char *pszOperand2, char *pszResult, size_t len )
{
size_t i = strlen( pszOperand1 );
size_t j = strlen( pszOperand2 );

if ( len < (max(i, j) +2 ) )
return;

size_t k = len;
pszResult[--k] = '';

short temp = 0;
short curso = 0;
while ( i > 0 || j > 0 )
{
  temp = curso;
  if ( i > 0 )
   temp += pszOperand1[--i] - '0';
  if ( j > 0 )
   temp += pszOperand2[--j] - '0';
  if ( temp > 10 )
  {
   pszResult[--k] = temp - 10 + '0';
   curso = 1;
  }
  else
  {
   pszResult[--k] = temp + '0';
   curso = 0;
  }
}
memmove( pszResult, pszResult + k, len - k );
}

测试用例：被加数与加数都是下面的120位整数
123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890

测试环境：
编译器：vs 2005
操作系统：windows7 64 bit
处理器：英特尔 Pentium(奔腾) G860 @ 3.00GHz 双核
内存：4 GB ( 金士顿 DDR3 1600MHz )

总结：Add2()函数比Add()函数在使用了memmove()优化后效率提升了36.28%，而空间节省了40%。