0

我想创建可以帮助我获得大于 MAXINT 的数字的代码。我听说我可以使用 Binary Code Decimal 来执行此操作，然后将较大数字的每两个十进制数（转换为 BCD）保留在 char 中。但是如何做到这一点？我应该将字符串作为输入，然后以某种方式将每个十进制数转换为 BCD？以及如何将两个转换后的十进制数字转换为一个字符？我是 C++ 新手，不知道该怎么做。

PS我不想使用“特殊”的库来解决这类问题。

4

1 回答 1

2

事实证明，这实际上非常简单。我们试着把它提升到一个新的水平怎么样？

下面是一个具有无限（或尽可能多的内存可以容纳）大小的 BCD 数的实现。它只支持正整数。我将把它扩展为支持负数（或实数）作为练习。

首先要做的事情：是的，我们希望将我们的数字作为一个字符串，然后从中构建它。由于它只是一个整数，这实际上很容易做到。我们主要创建一个辅助函数来帮助我们识别所有数字。

int char_to_int(const char c) {
  int ret = c - '0';
  if(ret > 9 || ret < 0) throw 1; // for simplicity. Use a class derived from std::exception instead.
  return ret;
}

我们现在可以尝试为我们的大数字实现输入和输出。

第一次尝试

有了那个助手，将字符串转换为 BCD 编码的缓冲区很容易。一个常见的实现可能如下所示：

int main() {
  unsigned char bignum[10]; // stores at most 20 BCD digits.
  std::memset(bignum, 0, sizeof(bignum));
  std::string input;
  std::cin >> input;
  try {
    if (input.size() > 20) throw 1; // Avoid problems with buffer overflow.
    for (int i=1;i<=input.size();i++) {
      int n = char_to_int(input[input.size()-i]);
      bignum[sizeof(bignum) - (i+1)/2] |= n << (i%2)*4; // These are bitwise operations. Google them!
    }
  }
  catch(int) {
    std::cout << "ERROR: Invalid input.\n";
    return 0; // Exit cleanly.
  }
  // bignum is now filled. Let's print it to prove.
  for (int i=0;i<sizeof(bignum);i++) {
    int first_digit = bignum[i] & '\x0F';     // Right side, doesn't need to shift.
    int second_digit = (bignum[i] & '\xF0')>>4; // Left side, shifted.
    std::cout << first_digit << second_digit;
  }
}

然而，这不是很节省空间。请注意，我们必须存储所有 20 位数字，即使我们的数字很小！如果我们需要 1000 位数字怎么办？如果我们需要 1000 个可能有也可能没有这 1000 位数字的数字怎么办？它也容易出错：我们必须记住初始化数组，并在转换之前进行边界检查以避免缓冲区溢出。

第二次尝试

我们可以使用 std::vector 改进我们的实现：

int main() {
  std::vector<unsigned char> bignum; // stores any quantity of digits.
  std::string input;
  std::cin >> input;
  try {
    // For an odd number of digits we want a trailling zero at the end.
    if(input.size()%2) n.num_vec.push_back(char_to_int(input[0]));
    for (unsigned i=input.size()%2;i<input.size();i+=2) {
      int left  = char_to_int(input[i]);
      int right = char_to_int(input[i+1]);
      n.num_vec.push_back(0);
      n.num_vec.back() = left << 4;
      n.num_vec.back() |= right;
    }

  }
  catch(int) {
    std::cout << "ERROR: Invalid input.\n";
    exit(0); // Exit cleanly.
  }
  // bignum is now filled. Let's print it to prove.
  for (unsigned i=0;i<bignum.size();++i) {
    // Notice that we inverted this from the previous one! Try to think why.
    int first_digit = (bignum[i] & '\xF0')>>4; // Left side, shifted.
    int second_digit = bignum[i] & '\x0F';     // Right side, doesn't need to shift.
    if(i || first_digit) std::cout << first_digit; // avoid printing trailling 0.
    std::cout << second_digit;
  }
}

看起来不错，就是太麻烦了。理想情况下，大数字用户不应该处理向量位置和所有那些胡说八道的东西。我们想编写行为如下的代码：

int main() {
  int a;
  cin >> a;
  cout << a;
}

它应该可以正常工作。

第三次尝试

事实证明这是可能的！只需使用一些有用的运算符将 bignum 包装到一个类中：

class bignum {
  std::vector<unsigned char> num_vec;
  template<typename T>
  friend T& operator<<(T& is, bignum& n);
  template<typename T>
  friend T& operator>>(T& os, bignum& n);
};

// Get input from any object that behaves like an std::istream (i.e.: std::cin)
template<typename T>
T& operator>>(T& is, bignum& n) {
  std::string input;
  is >> input;
  n.num_vec.reserve(input.size());
  if(input.size()%2) n.num_vec.push_back(char_to_int(input[0]));
  for (unsigned i=input.size()%2;i<input.size();i+=2) {
    int left  = char_to_int(input[i]);
    int right = (i+1) != input.size()?char_to_int(input[i+1]):0; // If odd number of digits, avoid getting garbage.
    n.num_vec.push_back(0);
    n.num_vec.back() = left << 4;
    n.num_vec.back() |= right;
  }
  return is;
}

// Output to any object that behaves like an std::ostream (i.e.: std::cout)
template<typename T>
T& operator<<(T& os, bignum& n) {
  for (unsigned i=0;i<n.num_vec.size();++i) {
    int first_digit = (n.num_vec[i] & '\xF0')>>4; // Left side, shifted.
    int second_digit = n.num_vec[i] & '\x0F';     // Right side, doesn't need to shift.
    if(i || first_digit) os << first_digit; // avoid printing trailling 0.
    os << second_digit;
  }
  return os;
}

然后我们的 main 函数看起来更具可读性：

int main() {
  bignum a;
  try {
    std::cin >> a;
  }
  catch(int) {
    std::cout << "ERROR: Invalid input.\n";
    return 0; // Exit cleanly.
  }
  std::cout << a;
}

结语

在这里，我们有了它。当然，没有加法，乘法等运算符，它不是很有用。我会把它们留作练习。代码，代码和代码，很快这对你来说就像小菜一碟。

请随时提出任何问题。好编码！

于 2015-04-20T17:51:22.130 回答