title: Implement BigInteger division
body: <p>I create a <code>BigInteger</code> class using an <code>std::string</code>. The interface is as follows:</p>
  
  <pre><code>class BigInteger
  {
  private:
      char sign;
      std::string digits;
      const std::size_t base = 10;
      short toDigit(int index) const {return index &gt;= 0 &amp;&amp; index &lt; digits.size() ? digits[index] - '0' : 0;}
  
  public:
      BigInteger();
      BigInteger(int value);
      BigInteger(int64_t value);
      BigInteger(const std::string &amp;value);
      BigInteger(const BigInteger &amp;other);
  
      inline bool isNegative() const {return sign == '-';}
      inline bool isPositive() const {return sign == '+';}
      inline bool isNeutral() const {return sign == '~';}
  
      bool operator &lt; (const BigInteger &amp;other) const;
      bool operator &gt; (const BigInteger &amp;other) const;
      bool operator &lt;= (const BigInteger &amp;other) const;
      bool operator &gt;= (const BigInteger &amp;other) const;
      bool operator == (const BigInteger &amp;other) const;
      bool operator != (const BigInteger &amp;other) const;
  
      BigInteger&amp; operator = (const BigInteger &amp;other);
      BigInteger&amp; operator += (const BigInteger &amp;other);
      BigInteger&amp; operator -= (const BigInteger &amp;other);
      BigInteger&amp; operator *= (const BigInteger &amp;other);
      BigInteger&amp; operator /= (const BigInteger &amp;other);
  
      BigInteger operator + (const BigInteger &amp;other) const;
      BigInteger operator - (const BigInteger &amp;other) const;
      BigInteger operator * (const BigInteger &amp;other) const;
      BigInteger operator / (const BigInteger &amp;other) const;
  
      BigInteger&amp; divide(const BigInteger &amp;D, BigInteger &amp;R);
  
      friend std::ostream&amp; operator &lt;&lt; (std::ostream&amp; os, const BigInteger&amp; other);
  };
  </code></pre>
  
  <p>Each character in the string, represents ONE digit.</p>
  
  <p>I implemented ALL operators except the <code>divide</code> function and the <code>division operator</code>.</p>
  
  <p>That's where I'm stuck! I was writing all my algorithms based off of Wikipedia explanations and came across the division algorithm that I like: </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_.28unsigned.29_with_remainder" rel="nofollow">https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_.28unsigned.29_with_remainder</a></p>
  
  <p>I like this one because it gives me the <code>quotient</code> and <code>remainder</code> and that will make implementing <code>modulo</code> easier.</p>
  
  <p>However, I don't have a shift operator and I'm not sure how to set the least significant bit of R to the bit in the numerator from my string. Any ideas how I can implement my <code>divide</code> function?</p>
  
  <p>I tried:</p>
  
  <pre><code>BigInteger&amp; BigInteger::divide(const BigInteger &amp;D, BigInteger &amp;R)
  {
      if (D.isNeutral()) //if D == 0.
      {
          throw std::overflow_error("Division By Zero Exception.");
      }
  
      R = 0;
      BigInteger Q = 0;
  
      for (std::size_t I = 0; I &lt; digits.size(); ++I)
      {
          R *= 2; //I believe this is the same as shifting left by 1.
          R.digits[0] = digits[I];
          if (R &gt;= D)
          {
              R -= D;
              Q.digits[I] = '1';
          }
      }
      *this = Q;
      return *this;
  }
  </code></pre>
  
  <p>Digits are stored backwards in the string. For example:</p>
  
  <p>value = 1024
  digits = 4201</p>
  
  <p>Any ideas what I need to do to get the BitShifting working and to get the division working? The division is more important to me.</p>