Big Integer class in C++. How to push digits in an array of unsigned long integers?

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开发者_StackOverflow;
};

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.

Before thinking about how to push digits, think about how to implement the four basic operations. What you want to do in the constructor from string is to convert the string to the internal representation, whatever that is, and to do so, you have to be able to multiply by 10 (supposing decimal) and add.

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;
}