I create a BigInteger
class using an std::string
. The interface is as follows:
class BigInteger
{
private:
char sign;
std::string digits;
const std::size_t base = 10;
short toDigit(int index) const {return index >= 0 && index < digits.size() ? digits[index] - '0' : 0;}
public:
BigInteger();
BigInteger(int value);
BigInteger(int64_t value);
BigInteger(const std::string &value);
BigInteger(const BigInteger &other);
inline bool isNegative() const {return sign == '-';}
inline bool isPositive() const {return sign == '+';}
inline bool isNeutral() const {return sign == '~';}
bool operator < (const BigInteger &other) const;
bool operator > (const BigInteger &other) const;
bool operator <= (const BigInteger &other) const;
bool operator >= (const BigInteger &other) const;
bool operator == (const BigInteger &other) const;
bool operator != (const BigInteger &other) const;
BigInteger& operator = (const BigInteger &other);
BigInteger& operator += (const BigInteger &other);
BigInteger& operator -= (const BigInteger &other);
BigInteger& operator *= (const BigInteger &other);
BigInteger& operator /= (const BigInteger &other);
BigInteger operator + (const BigInteger &other) const;
BigInteger operator - (const BigInteger &other) const;
BigInteger operator * (const BigInteger &other) const;
BigInteger operator / (const BigInteger &other) const;
BigInteger& divide(const BigInteger &D, BigInteger &R);
friend std::ostream& operator << (std::ostream& os, const BigInteger& other);
};
Each character in the string, represents ONE digit.
I implemented ALL operators except the divide
function and the division operator
.
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:
I like this one because it gives me the quotient
and remainder
and that will make implementing modulo
easier.
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 divide
function?
I tried:
BigInteger& BigInteger::divide(const BigInteger &D, BigInteger &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 < digits.size(); ++I)
{
R *= 2; //I believe this is the same as shifting left by 1.
R.digits[0] = digits[I];
if (R >= D)
{
R -= D;
Q.digits[I] = '1';
}
}
*this = Q;
return *this;
}
Digits are stored backwards in the string. For example:
value = 1024 digits = 4201
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.
Aucun commentaire:
Enregistrer un commentaire