#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
/*
实现十进制字符串转整形数组存储(算数操作性能高很多)
大数对小数进行 * / % <操作
大数的字符串打印
*/
#define BIGNUM_LEN 25
class BigNum
{
public:
BigNum()
{
memset(m_iNum, 0, sizeof(m_iNum));
m_iLen = 1;
}
BigNum(char* strDecimal)
{
int iLen = strlen(strDecimal);
unsigned char* strTemp = new unsigned char[iLen+1];
unsigned int leftDecimal = 0;
m_iLen = 0;
memset(m_iNum, 0, sizeof(m_iNum));
memset(strTemp, 0, iLen+1);
for (int i = 0; i < iLen; i++)
{
strTemp[i] = strDecimal[i] - '0';
}
while (iLen)
{
unsigned long long temp = 0;
for (int i = 0; i < iLen; i++)
{
temp *= 10;
temp += strTemp[i];
strTemp[i] = unsigned char(temp >> 32);
temp &= 0xffffffff;
}
m_iNum[m_iLen++] = unsigned int(temp);
bool bZero = true;
for (int i = 0; i < iLen; i++)
{
if (strTemp[i] != 0)
{
bZero = false;
memmove(strTemp, strTemp+i, iLen-i+1); // 包括结束符
iLen -= i;
break;
}
}
if(bZero)
{
iLen = 0;
break;
}
if (iLen < 9
|| (iLen == 9
&& (strTemp[0] < 4
|| strTemp[1] < 2
|| strTemp[2] < 9
|| strTemp[3] < 4
|| strTemp[4] < 9
|| strTemp[5] < 6
|| strTemp[6] < 7
|| strTemp[7] < 2
|| strTemp[8] < 9
|| strTemp[9] < 5))) // 0xffffffff 4294967295
{
for (int i = 0; i < iLen; i++)
{
strTemp[i] += '0';
}
m_iNum[m_iLen++] = _atoi64((char*)strTemp);
break;
}
}
}
BigNum operator*(const int& iM)
{
BigNum returnNum;
unsigned int upNum = 0;
for (unsigned char loopI = 0; loopI < m_iLen; loopI++)
{
unsigned long long res = m_iNum[loopI];
res *= iM;
res += upNum;
returnNum.m_iNum[loopI] = (unsigned int)(res & 0xffffffff);
upNum = (res>>32);
}
if(upNum)
{
//if(m_iLen == BIGNUM_LEN)
//{
// assert(upNum != 0, "overflow");
//}
returnNum.m_iNum[m_iLen] = upNum;
returnNum.m_iLen = m_iLen + 1;
}
else
{
returnNum.m_iLen = m_iLen;
}
return returnNum;
}
BigNum operator*=(const int& iM)
{
unsigned int upNum = 0;
for (unsigned char loopI = 0; loopI < m_iLen; loopI++)
{
unsigned long long res = m_iNum[loopI];
res *= iM;
res += upNum;
m_iNum[loopI] = (unsigned int)(res & 0xffffffff);
upNum = (res>>32);
}
if(upNum)
{
//if(m_iLen == BIGNUM_LEN)
//{
// assert(upNum != 0, "overflow");
//}
m_iNum[m_iLen++] = upNum;
}
else
{
m_iLen = m_iLen;
}
return (*this);
}
BigNum operator/(const int& iM)
{
BigNum returnNum;
unsigned int mod = 0;
for(char loopI = m_iLen-1; loopI >= 0; loopI--)
{
unsigned long long res = mod;
res = (res << 32) + m_iNum[loopI];
mod = res % iM;
returnNum.m_iNum[loopI] = (unsigned int)(res/iM);
}
if (returnNum.m_iNum[m_iLen-1] == 0)
{
returnNum.m_iLen = m_iLen-1;
}
else
{
returnNum.m_iLen = m_iLen;
}
if (returnNum.m_iLen == 0)
{
returnNum.m_iLen= 1;
}
return returnNum;
}
BigNum operator/=(const int& iM)
{
unsigned int mod = 0;
for(char loopI = m_iLen-1; loopI >= 0; loopI--)
{
unsigned long long res = mod;
res = (res << 32) + m_iNum[loopI];
mod = res % iM;
m_iNum[loopI] = (unsigned int)(res/iM);
}
while (m_iNum[m_iLen-1] == 0)
{
m_iLen--;
}
if (m_iLen == 0)
{
m_iLen= 1;
}
return (*this);
}
BigNum operator%(const int& iM)
{
BigNum returnNum;
unsigned int mod = 0;
for(char loopI = m_iLen-1; loopI >= 0; loopI--)
{
unsigned long long res = mod;
res = res << 32;
res += m_iNum[loopI];
mod = res % iM;
}
returnNum.m_iNum[0] = mod;
returnNum.m_iLen = 1;
return returnNum;
}
bool operator<(const BigNum& iB)
{
if(m_iLen < iB.m_iLen)
{
return true;
}
if(m_iLen > iB.m_iLen)
{
return false;
}
for (char loopI = m_iLen-1; loopI >= 0; loopI--)
{
if(m_iNum[loopI] < iB.m_iNum[loopI])
{
return true;
}
if(m_iNum[loopI] > iB.m_iNum[loopI])
{
return false;
}
}
return false;
}
public:
unsigned int m_iNum[BIGNUM_LEN]; // m_iNum[0] 存放着低位的数据
unsigned int m_iLen;
};
void PrintBN(BigNum& bN)
{
BigNum b0;
char strOut[2048] = {0};
for (int i = 0; i < 700, b0 < bN; i++)
{
strOut[i] = (bN % 10).m_iNum[0] + '0';
bN /= 10;
}
for (int i = strlen(strOut)-1; i >= 0; i--)
{
printf("%c", strOut[i]);
}
printf("\n");
}
int main()
{
char strTemp[2048] = {0};
char strInput[4][2048] = {0};
int iRet = 0;
while(gets(strTemp)
&& (iRet = sscanf(strTemp, "%s %s %s %s", strInput[0], strInput[1], strInput[2], strInput[3])) != EOF)
{
if(iRet == 1)
{
break;
}
if(iRet == 2)
{
// 测试转换
BigNum bN(strInput[1]);
printf("%s :", strInput[0]);
PrintBN(bN);
}
else if(iRet == 4)
{
BigNum bN(strInput[1]);
switch (strInput[2][0])
{
case '/':
if(strInput[2][1] == '=')
{
bN /= atoi(strInput[3]);
}
else
{
bN = bN / atoi(strInput[3]);
}
break;
case '*':
if(strInput[2][1] == '=')
{
bN *= atoi(strInput[3]);
}
else
{
bN = bN * atoi(strInput[3]);
}
break;
}
printf("%s:%s %s %s = ", strInput[0], strInput[1], strInput[2], strInput[3]);
PrintBN(bN);
}
}
return 0;
}
测试数据如下：
1 1
2 2
200000000 200000000
256 256
65535 65535
65536 65536
4294967295 4294967295
4294967296 4294967296
4294967900 4294967900
400000000000000000000000000000000000000000000 400000000000000000000000000000000000000000000
800000000000000000000000000000000000000000000 800000000000000000000000000000000000000000000
2 1 * 2
4 2 * 2
8589934590 4294967295 * 2
8589934590 4294967295 *= 2
4294967295 8589934590 / 2
4294967295 8589934590 /= 2
800000000000000000000000000000000000000000000 400000000000000000000000000000000000000000000 * 2
800000000000000000000000000000000000000000000 400000000000000000000000000000000000000000000 *= 2
400000000000000000000000000000000000000000000 800000000000000000000000000000000000000000000 / 2
400000000000000000000000000000000000000000000 800000000000000000000000000000000000000000000 /= 2
800000000000000000000000000000000000000000000000 400000000000000000000000000000000000000000000 * 2000
800000000000000000000000000000000000000000000000 400000000000000000000000000000000000000000000 *= 2000
400000000000000000000000000000000000000000000 800000000000000000000000000000000000000000000000 / 2000
400000000000000000000000000000000000000000000 800000000000000000000000000000000000000000000000 /= 2000