- Implement << and >> for BigUnsigned in response to email from Marco Schulze.
- Fix name: DOTR_ALIASED -> DTRT_ALIASED.
- Demonstrate all bitwise operators (&, |, ^, <<, >>) in sample.cc.
* stored (an "aliased" call), we risk overwriting the input before we read it.
* In this case, we first compute the result into a temporary BigUnsigned
* variable and then copy it into the requested output variable *this.
- * Each put-here operation uses the DOTR_ALIASED macro (Do The Right Thing on
+ * Each put-here operation uses the DTRT_ALIASED macro (Do The Right Thing on
* aliased calls) to generate code for this check.
*
* I adopted this approach on 2007.02.13 (see Assignment Operators in
* copy, but my reasoning would need to be verified very carefully. For now
* I'll leave in the copy.
*/
-#define DOTR_ALIASED(cond, op) \
+#define DTRT_ALIASED(cond, op) \
if (cond) { \
BigUnsigned tmpThis; \
tmpThis.op; \
// Addition
void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
- DOTR_ALIASED(this == &a || this == &b, add(a, b));
+ DTRT_ALIASED(this == &a || this == &b, add(a, b));
// If one argument is zero, copy the other.
if (a.len == 0) {
operator =(b);
// Subtraction
void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
- DOTR_ALIASED(this == &a || this == &b, subtract(a, b));
+ DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
// If b is zero, copy a. If a is shorter than b, the result is negative.
if (b.len == 0) {
operator =(a);
// Multiplication
void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
- DOTR_ALIASED(this == &a || this == &b, multiply(a, b));
+ DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
// If either a or b is zero, set to zero.
if (a.len == 0 || b.len == 0) {
len = 0;
// Bitwise and
void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
- DOTR_ALIASED(this == &a || this == &b, bitAnd(a, b));
+ DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b));
len = (a.len >= b.len) ? b.len : a.len;
allocate(len);
Index i;
// Bitwise or
void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
- DOTR_ALIASED(this == &a || this == &b, bitOr(a, b));
+ DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
Index i;
const BigUnsigned *a2, *b2;
if (a.len >= b.len) {
// Bitwise xor
void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
- DOTR_ALIASED(this == &a || this == &b, bitXor(a, b));
+ DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
Index i;
const BigUnsigned *a2, *b2;
if (a.len >= b.len) {
zapLeadingZeros();
}
+// Bitwise shift left
+void BigUnsigned::bitShiftLeft(const BigUnsigned &a, unsigned int b) {
+ DTRT_ALIASED(this == &a, bitShiftLeft(a, b));
+ Index shiftBlocks = b / N;
+ unsigned int shiftBits = b % N;
+ // + 1: room for high bits nudged left into another block
+ len = a.len + shiftBlocks + 1;
+ allocate(len);
+ Index i, j;
+ for (i = 0; i < shiftBlocks; i++)
+ blk[i] = 0;
+ for (j = 0, i = shiftBlocks; j <= a.len; j++, i++)
+ blk[i] = getShiftedBlock(a, j, shiftBits);
+ // Zap possible leading zero
+ if (blk[len - 1] == 0)
+ len--;
+}
+
+// Bitwise shift right
+void BigUnsigned::bitShiftRight(const BigUnsigned &a, unsigned int b) {
+ DTRT_ALIASED(this == &a, bitShiftRight(a, b));
+ // This calculation is wacky, but expressing the shift as a left bit shift
+ // within each block lets us use getShiftedBlock.
+ Index rightShiftBlocks = (b + N - 1) / N;
+ unsigned int leftShiftBits = N * rightShiftBlocks - b;
+ // Now (N * rightShiftBlocks - leftShiftBits) == b
+ // and 0 <= leftShiftBits < N.
+ if (rightShiftBlocks >= a.len + 1) {
+ // All of a is guaranteed to be shifted off, even considering the left
+ // bit shift.
+ len = 0;
+ return;
+ }
+ // Now we're allocating a positive amount.
+ // + 1: room for high bits nudged left into another block
+ len = a.len + 1 - rightShiftBlocks;
+ allocate(len);
+ Index i, j;
+ for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++)
+ blk[i] = getShiftedBlock(a, j, leftShiftBits);
+ // Zap possible leading zero
+ if (blk[len - 1] == 0)
+ len--;
+}
+
// INCREMENT/DECREMENT OPERATORS
// Prefix increment
// 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 might exist someday.
- //void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift
- //void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
+ void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift
+ void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
// NORMAL OPERATORS
// These perform the operation on this (to the left of the operator)
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
inline void BigUnsigned::operator ^=(const BigUnsigned &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
format, where `.N' goes `.2', `.3', etc. if there are multiple versions on the
same day. The topmost version listed is the one you have.
+2007.06.14
+----------
+- Implement << and >> for BigUnsigned in response to email from Marco Schulze.
+- Fix name: DOTR_ALIASED -> DTRT_ALIASED.
+- Demonstrate all bitwise operators (&, |, ^, <<, >>) in sample.cc.
+
2007.02.16
----------
Boris Dessy pointed out that the library threw an exception on "a *= a", so I changed all the put-here operations to handle aliased calls correctly using a temporary copy instead of throwing exceptions.
# Implicit rule to compile C++ files. Modify to your taste.
%.o : %.cc
- g++ -c -O -Wall -Wextra -pedantic $<
+ g++ -c -O2 -Wall -Wextra -pedantic $<
# Components of the library.
library-objects = BigUnsigned.o BigInteger.o BigUnsignedInABase.o BigIntegerUtils.o
* ``put-here operations''; see `BigUnsigned.hh' for details.
*/
BigInteger g(314159), h(265);
- // All five ``return-by-value'' operators.
+ // All five ``return-by-value'' arithmetic operators.
std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h)
<< '\n' << (g / h) << '\n' << (g % h) << std::endl;
+ BigUnsigned i(0xFF0000FF), j(0x0000FFFF);
+ // All five ``return-by-value'' bitwise operators.
+ std::cout.flags(std::ios::hex | std::ios::showbase);
+ std::cout << (i & j) << '\n' << (i | j) << '\n' << (i ^ j) << '\n'
+ << (j << 21) << '\n' << (j >> 10) << '\n';
+ std::cout.flags(std::ios::dec);
+
// Let's do some heavy lifting and calculate powers of 314.
int maxPower = 10;
BigUnsigned x(1), big314(314);
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff