学步园

// 大数乘法
//

http://topic.csdn.net/u/20110831/14/C60BF7C0-A789-4C89-B5DE-2F0FE13FFEE2.html

#include "stdafx.h"
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

// 数据类型
class BigInt
{
public:
 BigInt() : m_bSign(true) {}
 ~BigInt() {}
public:
 // 从字符串获得数据
 // strN的每个字符必须是 '0' ~ '9' 之一(第一个字符可以为 '-')
 bool FromString(const std::string& strN)
 {
  m_vNum.clear();
  for(std::string::const_reverse_iterator r_it = strN.rbegin();
   r_it != strN.rend(); ++r_it)
  {
   char c = *r_it;
   if(c == '-')
   {
    m_bSign = false;
    continue;
   }
   if(c < '0' || c > '9')
   {
    return false;
   }
   m_vNum.push_back(c-'0');
  }

  return standardization();
 }

 // 从数据获得字符串
 bool ToString(std::string& outStr)
 {
  outStr.clear();
  if(m_vNum.empty())
  {
   outStr.push_back('0');
   return true;
  }
  if(!m_bSign)
  {
   outStr.push_back('-');
  }

  for(std::vector<int>::const_reverse_iterator r_it = m_vNum.rbegin();
   r_it != m_vNum.rend(); ++r_it)
  {
   int n = *r_it;
   if(n<0 || n>9)
   {
    return false;
   }
   outStr.push_back('0'+n);
  }

  return true;
 }

 // 乘法
 BigInt operator*(const BigInt& second)
 {
  BigInt ret;
  int iLen0 = m_vNum.size();
  int iLen1 = second.m_vNum.size();
  if(iLen0 == 0 || iLen1==0)
  {
   return ret;
  }
  ret.m_bSign = (m_bSign == second.m_bSign);

  int iLen = 0;
  for(int i=0; i<iLen0; ++i)
  {
   int n0 = m_vNum[i];
   for(int j=0; j<iLen1; ++j)
   {
    int n1 = second.m_vNum[j];
    int n = n0 * n1;
    if(iLen <= i+j)
     ret.m_vNum.push_back(0);

    ret.m_vNum[i+j] += n;
   }
  }

  ret.standardization();
  return ret;
 }

private:
 // 规范化
 // 将每个位规范到 0~9,并去除最后无用的0
 bool standardization()
 {
  // 规范到0-9
  int nLen = m_vNum.size();
  for(int i=0; i<nLen; ++i)
  {
   int n = m_vNum[i];
   if(n < 0)
    return false;
   if(n <= 9)
    continue;

   if(i+1 == nLen)
   {
    // 最后一位
    m_vNum.push_back(0);
    nLen++;
   }
   m_vNum[i] = n%10;
   m_vNum[i+1] += n/10;
  }

  // 去掉末尾的0
  while(!m_vNum.empty() && m_vNum[m_vNum.size()-1] == 0)
   m_vNum.pop_back();

  if(m_vNum.empty())
   m_bSign = true;

  return true;
 }

private:
 // 符号位, 0和正数为true, 负数为false
 bool m_bSign;
 // 每个数表示一个十进制位, 低位放在前面
 std::vector<int> m_vNum;
};

int _tmain(int argc, _TCHAR* argv[])
{
 std::string str1 = "1234567891011121314151617181920";
 std::string str2 = "2019181716151413121110987654321";
 
 BigInt n1, n2, n3;
 n1.FromString(str1);
 n2.FromString(str2);
 n3 = n1 * n2;

 std::string str3;
 n3.ToString(str3);

 std::cout << "// 输出" << std::endl;
 std::cout << "// " << str1 << " * " << str2 << " = " << std::endl;
 std::cout << "// " << str3 << std::endl;
 return 0;
}

// 输出
// 1234567891011121314151617181920 * 2019181716151413121110987654321 =
// 2492816912877266687794240983772975935013386905490061131076320