/*
* Matt McCutchen's Big Integer Library
-* http://hashproduct.metaesthetics.net/bigint/
*/
#ifndef BIGUNSIGNED
* c = a + b; // Now c == 50.
* c.add(a, b); // Same effect but without the two bulk-copies.
* c.divideWithRemainder(b, d); // 50 / 7; now d == 7 (quotient) and c == 1 (remainder).
- * a.add(a, b); // Unsafe ``aliased'' call; causes a runtime error.
+ * a.add(a, b); // ``Aliased'' calls now do the right thing using a
+ * // temporary copy, but see note on divideWithRemainder.
*/
// PUT-HERE OPERATIONS
* and these differ from the semantics of primitive-type
* / and % under division by zero.
* Look in `BigUnsigned.cc' for details.
+ * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
+ * sense to write quotient and remainder into the same variable.
*/
void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q);
void divide(const BigUnsigned &a, const BigUnsigned &b) {
- // Division, deprecated and provided for backward compatibility
BigUnsigned a2(a);
a2.divideWithRemainder(b, *this);
// quotient now in *this
// don't care about remainder left in a2
}
void modulo(const BigUnsigned &a, const BigUnsigned &b) {
- // Modular reduction, deprecated and provided for backward compatibility
*this = a;
BigUnsigned q;
divideWithRemainder(b, q);
// remainder now in *this
// don't care about quotient left in q
}
- // Bitwise operations. Two read-only operands as arguments. Result left in *this.
+ // Bitwise operations. Result left in *this.
// These are not provided for BigIntegers; I think that using them on BigIntegers
// will discard the sign first.
void bitAnd(const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND
void bitOr(const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR
void bitXor(const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR
-
- // These functions are declared but not defined. (Sorry.)
- // Trying to call either will result in a link-time error.
void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift
void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
BigUnsigned operator &(const BigUnsigned &x) const; // Bitwise AND
BigUnsigned operator |(const BigUnsigned &x) const; // Bitwise OR
BigUnsigned operator ^(const BigUnsigned &x) const; // Bitwise XOR
+ BigUnsigned operator <<(unsigned int b) const; // Bitwise left shift
+ BigUnsigned operator >>(unsigned int b) const; // Bitwise right shift
+ // Additional operators in an attempt to avoid overloading tangles.
+ BigUnsigned operator <<(int b) const;
+ BigUnsigned operator >>(int b) const;
// ASSIGNMENT OPERATORS
// These perform the operation on this and x, storing the result into this.
void operator &=(const BigUnsigned &x); // Bitwise AND
void operator |=(const BigUnsigned &x); // Bitwise OR
void operator ^=(const BigUnsigned &x); // Bitwise XOR
+ void operator <<=(unsigned int b); // Bitwise left shift
+ void operator >>=(unsigned int b); // Bitwise right shift
+ // Additional operators in an attempt to avoid overloading tangles.
+ void operator <<=(int b);
+ void operator >>=(int b);
// INCREMENT/DECREMENT OPERATORS
// These increase or decrease the number by 1. To discourage side effects,
ans.bitXor(*this, x);
return ans;
}
+inline BigUnsigned BigUnsigned::operator <<(unsigned int b) const {
+ BigUnsigned ans;
+ ans.bitShiftLeft(*this, b);
+ return ans;
+}
+inline BigUnsigned BigUnsigned::operator >>(unsigned int b) const {
+ BigUnsigned ans;
+ ans.bitShiftRight(*this, b);
+ return ans;
+}
+inline BigUnsigned BigUnsigned::operator <<(int b) const {
+ if (b < 0)
+ throw "BigUnsigned::operator <<(int): Negative shift amounts are not supported";
+ return *this << (unsigned int)(b);
+}
+inline BigUnsigned BigUnsigned::operator >>(int b) const {
+ if (b < 0)
+ throw "BigUnsigned::operator >>(int): Negative shift amounts are not supported";
+ return *this >> (unsigned int)(b);
+}
-// ASSIGNMENT OPERATORS
-// These create a copy of this, then invoke the appropriate
-// put-here operation on this, passing the copy and x.
-// Exception: those updated for divideWithRemainder.
+/*
+ * ASSIGNMENT OPERATORS
+ *
+ * Now the responsibility for making a temporary copy if necessary
+ * belongs to the put-here operations. I made this change on 2007.02.13 after
+ * Boris Dessy pointed out that the old implementation handled calls like
+ * "a *= a" badly: it translated them to essentially "a.multiply(aCopy, a)",
+ * which threw an exception.
+ */
inline void BigUnsigned::operator +=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- add(thisCopy, x);
+ add(*this, x);
}
inline void BigUnsigned::operator -=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- subtract(thisCopy, x);
+ subtract(*this, x);
}
inline void BigUnsigned::operator *=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- multiply(thisCopy, x);
+ multiply(*this, x);
}
inline void BigUnsigned::operator /=(const BigUnsigned &x) {
// Updated for divideWithRemainder
// don't care about quotient left in q
}
inline void BigUnsigned::operator &=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- bitAnd(thisCopy, x);
+ bitAnd(*this, x);
}
inline void BigUnsigned::operator |=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- bitOr(thisCopy, x);
+ bitOr(*this, x);
}
inline void BigUnsigned::operator ^=(const BigUnsigned &x) {
- BigUnsigned thisCopy(*this);
- bitXor(thisCopy, x);
+ bitXor(*this, x);
+}
+inline void BigUnsigned::operator <<=(unsigned int b) {
+ bitShiftLeft(*this, b);
+}
+inline void BigUnsigned::operator >>=(unsigned int b) {
+ bitShiftRight(*this, b);
+}
+inline void BigUnsigned::operator <<=(int b) {
+ if (b < 0)
+ throw "BigUnsigned::operator <<=(int): Negative shift amounts are not supported";
+ *this <<= (unsigned int)(b);
+}
+inline void BigUnsigned::operator >>=(int b) {
+ if (b < 0)
+ throw "BigUnsigned::operator >>=(int): Negative shift amounts are not supported";
+ *this >>= (unsigned int)(b);
}
#endif