C++ 中的大整数类。如何将数字推入无符号长整数数组中？

发布于 2024-10-27 00:08:23 字数 465 浏览 2 评论 0原文

我正在编写一个简单的大整数库来进行练习。我想在 RSA 的简单实现中使用它。我已阅读之前的所有主题，但尚未找到我的问题的答案。我刚刚开始项目，我已经读过表示大整数的所有数字的最佳选择应该是使用无符号长数字数组来表示它们，所以它应该是这样的：

class BigInteger
{
   public:
      BigInteger(const std::string &digits);

   private:
      std::vector <unsigned long> _digits;
};

问题是我不知道如何实现类的构造函数。我认为我应该转换字符串的每个字符并将其保存在数组中，以最小化数组使用的总体内存的方式，因为每个字符都是 1 个字节长，而无符号 long 至少有 4 个字节长。我是否应该一次推送一组 4 个字符以避免浪费每个无符号长数字内存？你能给我一个例子或者一些建议吗？

谢谢。

原文

I am writing a simple big integer library for exercise. I would like to use it in a simple implementation of RSA. I have read all the previous threads but I have not found an answer to my question. I am just at the beginning of the project and I have read the best choice to represents all the digits of the big integer should be to represent them using an array of unsigned long numbers, so it should be something like this:

class BigInteger
{
   public:
      BigInteger(const std::string &digits);

   private:
      std::vector <unsigned long> _digits;
};

The problem is that I don't know how to implement the constructor of the class. I think I should convert every character of the string and save it in the array in a way which minimizes the overall memory used by the array because every character is 1 byte long while an unsigned long is at least 4 bytes long. Should I push a group of 4 characters at a time to avoid wasting every unsigned long digit memory? Could you give me an example or some suggestions?

Thank you.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

凹づ凸ル 2024-11-03 00:08:23

在思考如何推送数字之前，先思考如何实现
四个基本操作。你想在构造函数中做什么
string 是将字符串转换为内部表示形式，无论什么
也就是说，要做到这一点，您必须能够乘以 10（假设
小数）并相加。

回复收藏 0 原文

羁绊已千年 2024-11-03 00:08:23

正如 @James Kanze 正确指出的那样，字符串的转换不是主要的设计问题，您应该将它们留到最后。如果您专注于简化与外界的接口，您最终可能会得到一个易于序列化但使用起来却是一场噩梦的设计。

对于当前的特定问题，有效处理大数的常见方法是使用每个存储单元中的一半位（如果您的 unsigned long 是 32 位，则仅使用较低的 16 位）。所有单元中都有空闲空间，允许您在每个元素中单独操作，而不必处理溢出，然后通过移动进位（高位数字）来标准化结果。一种简化的伪代码求和方法（忽略大小和大多数其他内容）：

bignumber& bignumber::operator+=( bignumber const & rhs ) {
   // ensure that there is enough space
   for ( int i = 0; i < size(); ++i ) {
      data[ i ] += rhs.data[ i ];       // might break invariant but won't overflow
   }
   normalize();                         // fix the invariant
}
// Common idiom: implement operator+ in terms of operator+= on the first argument 
//     (copied by value)
bignumber operator+( bignumber lhs, bignumber const & rhs ) {
   lhs += rhs;
   return lhs;
}

As @James Kanze correctly points out, conversions to and from string are not the main design issue, and you should leave them until the end. If you focus on simplifying the interface with the outside world you might end up with a design that is easy to serialize but a nightmare to work with.

On the particular problem at hand, a common approach to dealing with bignumbers efficiently is using half of the bits in each storage unit (if your unsigned long is 32bits, use only the lower 16bits). Having the spare space in all units allow you to operate separatedly in each element without having to deal with overflows and then normalize the result by moving the carry-out (high bit numbers). A simplified pseuso-code approach to sum (ignoring sizes and mostly everything else would be:

bignumber& bignumber::operator+=( bignumber const & rhs ) {
   // ensure that there is enough space
   for ( int i = 0; i < size(); ++i ) {
      data[ i ] += rhs.data[ i ];       // might break invariant but won't overflow
   }
   normalize();                         // fix the invariant
}
// Common idiom: implement operator+ in terms of operator+= on the first argument 
//     (copied by value)
bignumber operator+( bignumber lhs, bignumber const & rhs ) {
   lhs += rhs;
   return lhs;
}

回复收藏 0 原文

~没有更多了~