+/*
+* Matt McCutchen's Big Integer Library
+* http://mysite.verizon.net/mccutchen/bigint/
+*/
+
+#include "BigUnsigned.h"
+
+// MANAGEMENT
+
+// This routine is called to ensure the number array is at least a
+// certain size before the result of an operation is written over it.
+void BigUnsigned::allocate(BlkNum c) {
+ // If the requested capacity is more than the current capacity...
+ if (c > cap) {
+ // Delete the old number array
+ delete [] blk;
+ // Allocate the new array
+ cap = c;
+ blk = new Blk[cap];
+ }
+}
+
+// This routine is called to ensure the number array is at least a
+// certain size without losing its contents.
+void BigUnsigned::allocateAndCopy(BlkNum c) {
+ // If the requested capacity is more than the current capacity...
+ if (c > cap) {
+ Blk *oldBlk = blk;
+ // Allocate the new number array
+ cap = c;
+ blk = new Blk[cap];
+ // Copy number blocks
+ BlkNum i;
+ Blk *blkI;
+ const Blk *oldBlkI;
+ for (i = 0, blkI = blk, oldBlkI = oldBlk; i < len; i++, blkI++, oldBlkI++)
+ *blkI = *oldBlkI;
+ // Delete the old array
+ delete [] oldBlk;
+ }
+}
+
+// Copy constructor
+BigUnsigned::BigUnsigned(const BigUnsigned &x) : len(x.len) {
+ // Create number array
+ cap = len;
+ blk = new Blk[cap];
+ // Copy number blocks
+ BlkNum i;
+ Blk *blkI;
+ const Blk *xBlkI;
+ for (i = 0, blkI = blk, xBlkI = x.blk; i < len; i++, blkI++, xBlkI++)
+ *blkI = *xBlkI;
+}
+
+// Assignment operator
+void BigUnsigned::operator=(const BigUnsigned &x) {
+ // Calls like a = a have no effect
+ if (this == &x)
+ return;
+ // Copy length
+ len = x.len;
+ // Expand number array if necessary
+ allocate(len);
+ // Copy number blocks
+ BlkNum i;
+ Blk *blkI;
+ const Blk *xBlkI;
+ for (i = 0, blkI = blk, xBlkI = x.blk; i < len; i++, blkI++, xBlkI++)
+ *blkI = *xBlkI;
+}
+
+// Constructor from an array of blocks
+BigUnsigned::BigUnsigned(const Blk *b, BlkNum l) : cap(l), len(l) {
+ // Create number array
+ blk = new Blk[cap];
+ // Copy number blocks
+ BlkNum i;
+ Blk *blkI;
+ const Blk *bI;
+ for (i = 0, blkI = blk, bI = b; i < len; i++, blkI++, bI++)
+ *blkI = *bI;
+ zapLeadingZeros();
+}
+
+/*
+* The steps for construction of a BigUnsigned
+* from an integral value x are as follows:
+* 1. If x is zero, create an empty BigUnsigned and stop.
+* 2. If x is negative, throw an exception.
+* 3. Allocate a one-block number array.
+* 4. If x is of a signed type, convert x to the unsigned
+* type of the same length.
+* 5. Expand x to a Blk, and store it in the number array.
+*/
+
+BigUnsigned::BigUnsigned(unsigned long x) {
+ if (x == 0) {
+ cap = 0;
+ blk = new Blk[0];
+ len = 0;
+ } else {
+ cap = 1;
+ blk = new Blk[1];
+ len = 1;
+ *blk = Blk(x);
+ }
+}
+
+BigUnsigned::BigUnsigned(long x) {
+ if (x == 0) {
+ cap = 0;
+ blk = new Blk[0];
+ len = 0;
+ } else if (x > 0) {
+ cap = 1;
+ blk = new Blk[1];
+ len = 1;
+ *blk = Blk(x);
+ } else
+ throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number";
+}
+
+BigUnsigned::BigUnsigned(unsigned int x) {
+ if (x == 0) {
+ cap = 0;
+ blk = new Blk[0];
+ len = 0;
+ } else {
+ cap = 1;
+ blk = new Blk[1];
+ len = 1;
+ *blk = Blk(x);
+ }
+}
+
+BigUnsigned::BigUnsigned(int x) {
+ if (x == 0) {
+ cap = 0;
+ blk = new Blk[0];
+ len = 0;
+ } else if (x > 0) {
+ cap = 1;
+ blk = new Blk[1];
+ len = 1;
+ *blk = Blk(x);
+ } else
+ throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number";
+}
+
+BigUnsigned::BigUnsigned(unsigned short x) {
+ if (x == 0) {
+ cap = 0;
+ blk = new Blk[0];
+ len = 0;
+ } else {
+ cap = 1;
+ blk = new Blk[1];
+ len = 1;
+ *blk = Blk(x);
+ }
+}
+
+BigUnsigned::BigUnsigned(short x) {
+ if (x == 0) {
+ cap = 0;
+ blk = new Blk[0];
+ len = 0;
+ } else if (x > 0) {
+ cap = 1;
+ blk = new Blk[1];
+ len = 1;
+ *blk = Blk(x);
+ } else
+ throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number";
+}
+
+// CONVERTERS
+/*
+* The steps for conversion of a BigUnsigned to an
+* integral type are as follows:
+* 1. If the BigUnsigned is zero, return zero.
+* 2. If it is more than one block long or its lowest
+* block has bits set out of the range of the target
+* type, throw an exception.
+* 3. Otherwise, convert the lowest block to the
+* target type and return it.
+*/
+
+namespace {
+ // These masks are used to test whether a Blk has bits
+ // set out of the range of a smaller integral type. Note
+ // that this range is not considered to include the sign bit.
+ const BigUnsigned::Blk lMask = ~0 >> 1;
+ const BigUnsigned::Blk uiMask = (unsigned int)(~0);
+ const BigUnsigned::Blk iMask = uiMask >> 1;
+ const BigUnsigned::Blk usMask = (unsigned short)(~0);
+ const BigUnsigned::Blk sMask = usMask >> 1;
+}
+
+BigUnsigned::operator unsigned long() const {
+ if (len == 0)
+ return 0;
+ else if (len == 1)
+ return (unsigned long) *blk;
+ else
+ throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long";
+}
+
+BigUnsigned::operator long() const {
+ if (len == 0)
+ return 0;
+ else if (len == 1 && (*blk & lMask) == *blk)
+ return (long) *blk;
+ else
+ throw "BigUnsigned::operator long: Value is too big for a long";
+}
+
+BigUnsigned::operator unsigned int() const {
+ if (len == 0)
+ return 0;
+ else if (len == 1 && (*blk & uiMask) == *blk)
+ return (unsigned int) *blk;
+ else
+ throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int";
+}
+
+BigUnsigned::operator int() const {
+ if (len == 0)
+ return 0;
+ else if (len == 1 && (*blk & iMask) == *blk)
+ return (int) *blk;
+ else
+ throw "BigUnsigned::operator int: Value is too big for an int";
+}
+
+BigUnsigned::operator unsigned short() const {
+ if (len == 0)
+ return 0;
+ else if (len == 1 && (*blk & usMask) == *blk)
+ return (unsigned short) *blk;
+ else
+ throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short";
+}
+
+BigUnsigned::operator short() const {
+ if (len == 0)
+ return 0;
+ else if (len == 1 && (*blk & sMask) == *blk)
+ return (short) *blk;
+ else
+ throw "BigUnsigned::operator short: Value is too big for a short";
+}
+
+// COMPARISON
+BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
+ // A bigger length implies a bigger number.
+ if (len < x.len)
+ return less;
+ else if (len > x.len)
+ return greater;
+ else {
+ // Compare blocks one by one from left to right.
+ BlkNum i = len;
+ const Blk *blkI = blk + len;
+ const Blk *xBlkI = x.blk + len;
+ while (i > 0) {
+ i--;
+ blkI--;
+ xBlkI--;
+ if (*blkI == *xBlkI)
+ continue;
+ else if (*blkI > *xBlkI)
+ return greater;
+ else
+ return less;
+ }
+ // If no blocks differed, the numbers are equal.
+ return equal;
+ }
+}
+
+// PUT-HERE OPERATIONS
+
+// Addition
+void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::add: One of the arguments is the invoked object";
+ // If one argument is zero, copy the other.
+ if (a.len == 0) {
+ operator =(b);
+ return;
+ } else if (b.len == 0) {
+ operator =(a);
+ return;
+ }
+ // Carries in and out of an addition stage
+ bool carryIn, carryOut;
+ Blk temp;
+ BlkNum i;
+ // a2 points to the longer input, b2 points to the shorter
+ const BigUnsigned *a2, *b2;
+ if (a.len >= b.len) {
+ a2 = &a;
+ b2 = &b;
+ } else {
+ a2 = &b;
+ b2 = &a;
+ }
+ // These point directly to the position of interest in the
+ // corresponding block arrays, for faster access.
+ Blk *blkI;
+ const Blk *a2BlkI, *b2BlkI;
+ // Set prelimiary length and make room in this BigUnsigned
+ len = a2->len + 1;
+ allocate(len);
+ // For each block index that is present in both inputs...
+ for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk,
+ carryIn = false; i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++) {
+ // Add input blocks
+ temp = *a2BlkI + *b2BlkI;
+ // If a rollover occurred, the result is less than either input.
+ // This test is used many times in the BigUnsigned code.
+ carryOut = (temp < *a2BlkI);
+ // If a carry was input, handle it
+ if (carryIn) {
+ temp++;
+ carryOut |= (temp == 0);
+ }
+ *blkI = temp; // Save the addition result
+ carryIn = carryOut; // Pass the carry along
+ }
+ // If there is a carry left over, increase blocks until
+ // one does not roll over.
+ for (; i < a2->len && carryIn; i++, blkI++, a2BlkI++) {
+ temp = *a2BlkI + 1;
+ carryIn = (temp == 0);
+ *blkI = temp;
+ }
+ // If the carry was resolved but the larger number
+ // still has blocks, copy them over.
+ for (; i < a2->len; i++, blkI++, a2BlkI++)
+ *blkI = *a2BlkI;
+ // Set the extra block if there's still a carry, decrease length otherwise
+ if (carryIn)
+ *blkI = 1;
+ else
+ len--;
+}
+
+// Subtraction
+void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::subtract: One of the arguments is the invoked object";
+ // If b is zero, copy a. If a is shorter than b, the result is negative.
+ if (b.len == 0) {
+ operator =(a);
+ return;
+ } else if (a.len < b.len)
+ throw "BigUnsigned::subtract: Negative result in unsigned calculation";
+ bool borrowIn, borrowOut;
+ Blk temp;
+ BlkNum i;
+ // These point directly to the position of interest in the
+ // corresponding block arrays, for faster access.
+ Blk *blkI;
+ const Blk *aBlkI, *bBlkI;
+ // Set preliminary length and make room
+ len = a.len;
+ allocate(len);
+ // For each block index that is present in both inputs...
+ for (i = 0, blkI = blk, aBlkI = a.blk, bBlkI = b.blk,
+ borrowIn = false; i < b.len; i++, blkI++, aBlkI++, bBlkI++) {
+ temp = *aBlkI - *bBlkI;
+ // If a reverse rollover occurred, the result is greater than the block from a.
+ borrowOut = (temp > *aBlkI);
+ // Handle an incoming borrow
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ *blkI = temp; // Save the subtraction result
+ borrowIn = borrowOut; // Pass the borrow along
+ }
+ // If there is a borrow left over, decrease blocks until
+ // one does not reverse rollover.
+ for (; i < a.len && borrowIn; i++, blkI++, aBlkI++) {
+ borrowIn = (*aBlkI == 0);
+ *blkI = *aBlkI - 1;
+ }
+ // If there's still a borrow, the result is negative.
+ // Throw an exception, but zero out this object first.
+ if (borrowIn) {
+ len = 0;
+ throw "BigUnsigned::subtract: Negative result in unsigned calculation";
+ } else // Copy over the rest of the blocks
+ for (; i < a.len; i++, blkI++, aBlkI++)
+ *blkI = *aBlkI;
+ // Zap leading zeros
+ zapLeadingZeros();
+}
+
+// Multiplication
+void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::multiply: One of the arguments is the invoked object";
+ // If either a or b is zero, set to zero.
+ if (a.len == 0 || b.len == 0) {
+ len = 0;
+ return;
+ }
+ // Overall method: this = 0, then for each 1-bit of a, add b
+ // to this shifted the appropriate amount.
+ // Variables for the calculation
+ BlkNum i, j;
+ unsigned int i2;
+ Blk aBlk, bHigh, temp;
+ bool carryIn, carryOut;
+ // These point directly to the positions of interest in the
+ // corresponding block arrays, for faster access.
+ Blk *blkI, *blkK;
+ const Blk *aBlkI, *bBlkJ;
+ // Set preliminary length and make room
+ len = a.len + b.len;
+ allocate(len);
+ // Zero out this object
+ for (i = 0, blkI = blk; i < len; i++, blkI++)
+ *blkI = 0;
+ // For each block of the first number...
+ for (i = 0, blkI = blk, aBlkI = a.blk; i < a.len; i++, blkI++, aBlkI++)
+ // For each 1-bit of that block...
+ for (i2 = 0, aBlk = *aBlkI; aBlk != 0; i2++, aBlk >>= 1) {
+ if ((aBlk & 1) == 0)
+ continue;
+ /* Add b to this, shifted left i blocks and i2 bits.
+ * j is the index in b, and k = i + j is the index in this.
+ * The low bits of b.blk[j] are shifted and added to blk[k].
+ * bHigh is used to carry the high bits to the next addition. */
+ carryIn = false;
+ bHigh = 0;
+ for (j = 0, bBlkJ = b.blk, blkK = blkI; j < b.len; j++, bBlkJ++, blkK++) {
+ temp = *blkK + ((*bBlkJ << i2) | bHigh);
+ carryOut = (temp < *blkK);
+ if (carryIn) {
+ temp++;
+ carryOut |= (temp == 0);
+ }
+ *blkK = temp;
+ carryIn = carryOut;
+ bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2);
+ }
+ temp = *blkK + bHigh;
+ carryOut = (temp < *blkK);
+ if (carryIn) {
+ temp++;
+ carryOut |= (temp == 0);
+ }
+ *blkK = temp;
+ carryIn = carryOut;
+ for (; carryIn; blkK++) {
+ (*blkK)++;
+ carryIn = (*blkK == 0);
+ }
+ }
+ // Zap leading zero
+ if (blk[len - 1] == 0)
+ len--;
+}
+
+// Division
+void BigUnsigned::divide(const BigUnsigned &a, const BigUnsigned &b) {
+ // Note: This is integer division. Any fractional part
+ // of the result is truncated.
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::divide: One of the arguments is the invoked object";
+ // If b is zero, throw an exception. If a is zero, set to zero.
+ else if (b.len == 0)
+ throw "BigUnsigned::divide: Division by zero";
+ else if (a.len < b.len) {
+ len = 0;
+ return;
+ }
+ /* Overall method: Subtract b, shifted varying amounts to
+ * the left, from a, setting the bit in the quotient
+ * whenever the subtraction succeeds. */
+ // Variables for the calculation
+ BlkNum i, j, k;
+ unsigned int i2;
+ Blk bHigh, temp;
+ bool borrowIn, borrowOut;
+ // work1 is a copy of a that can be modified
+ // after each successful subtraction.
+ Blk *work1 = new Blk[a.len + 1];
+ Blk *work1I = work1;
+ const Blk *aBlkI = a.blk;
+ for (i = 0; i < a.len; i++, work1I++, aBlkI++)
+ *work1I = *aBlkI;
+ *work1I = 0;
+ // work2 holds part of the result of a subtraction
+ Blk *work2 = new Blk[a.len + 1];
+ // These point directly to the positions of interest in the
+ // corresponding block arrays, for faster access.
+ Blk *blkI, *work1K, *work2J;
+ const Blk *bBlkJ;
+ // Set preliminary length and make room
+ len = a.len - b.len + 1;
+ allocate(len);
+ // For each possible left-shift of b in blocks...
+ i = len;
+ blkI = blk + len;
+ work1I = work1 + len;
+ while (i > 0) {
+ i--;
+ blkI--;
+ work1I--;
+ // For each possible left-shift of b in bits...
+ *blkI = 0;
+ i2 = 8 * sizeof(Blk);
+ while (i2 > 0) {
+ i2--;
+ // Subtract b, shifted left i blocks and i2 bits, from work1
+ // and store the answer in work2. See note in BigUnsigned::multiply.
+ bHigh = 0;
+ for (j = 0, bBlkJ = b.blk, work2J = work2, k = i, work1K = work1I,
+ borrowIn = false; j < b.len; j++, bBlkJ++, work2J++, k++, work1K++) {
+ temp = *work1K - ((*bBlkJ << i2) | bHigh);
+ borrowOut = (temp > *work1K);
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ *work2J = temp;
+ borrowIn = borrowOut;
+ bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2);
+ }
+ temp = *work1K - bHigh;
+ borrowOut = (temp > *work1K);
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ *work2J = temp;
+ borrowIn = borrowOut;
+ j++;
+ work2J++;
+ k++;
+ work1K++;
+ for (; k < a.len + 1 && borrowIn; j++, work2J++, k++, work1K++) {
+ borrowIn = (*work1K == 0);
+ *work2J = *work1K - 1;
+ }
+ /* If the subtraction was performed successfully, set bit i2
+ * in block i of the quotient, and copy the changed portion of
+ * work2 back to work1. Otherwise, reset that bit and move on. */
+ if (!borrowIn) {
+ *blkI |= (1 << i2);
+ while (j > 0) {
+ j--;
+ work2J--;
+ k--;
+ work1K--;
+ *work1K = *work2J;
+ }
+ }
+ }
+ }
+ // Zap leading zero
+ if (blk[len - 1] == 0)
+ len--;
+ // Deallocate temporary arrays.
+ // (Thanks to Brad Spencer for noticing my accidental omission of this!)
+ delete [] work1;
+ delete [] work2;
+}
+
+// Modulo
+void BigUnsigned::modulo(const BigUnsigned &a, const BigUnsigned &b) {
+ /* Note that the mathematical definition of mod is somewhat
+ * different from the way the normal C++ % operator behaves.
+ * This function does it the mathematical way. */
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::modulo: One of the arguments is the invoked object";
+ // If b is zero, copy a and return. By the mathematical definition,
+ // x mod 0 = x, though the normal C++ % would throw an exception.
+ else if (b.len == 0) {
+ len = 0;
+ return;
+ // If a is zero, set to zero and return.
+ } else if (a.len < b.len) {
+ operator =(a);
+ return;
+ }
+ /* Overall method: Copy a into this. Then subtract b,
+ * shifted varying amounts to the left, from this.
+ * When no more subtraction is possible, stop; this
+ * will contain the remainder.
+ * This is very similar to the division routine, except
+ * that whether or not a subtraction succeeds is ignored,
+ * and "this" serves the purpose of work1. */
+ // Variables for the calculation
+ BlkNum i, j, k;
+ unsigned int i2;
+ Blk bHigh, temp;
+ bool borrowIn, borrowOut;
+ allocate(a.len + 1);
+ operator =(a);
+ blk[len] = 0;
+ // work2 holds part of the result of a subtraction
+ Blk *work2 = new Blk[a.len + 1];
+ // These point directly to the positions of interest in the
+ // corresponding block arrays, for faster access.
+ Blk *blkI, *blkK, *work2J;
+ const Blk *bBlkJ;
+ // For each possible left-shift of b in blocks...
+ i = len;
+ blkI = blk + len;
+ while (i > 0) {
+ i--;
+ blkI--;
+ // For each possible left-shift of b in bits...
+ i2 = 8 * sizeof(Blk);
+ while (i2 > 0) {
+ i2--;
+ // Subtract b, shifted left i blocks and i2 bits, from work1
+ // and store the answer in work2. See note in BigUnsigned::multiply.
+ bHigh = 0;
+ for (j = 0, bBlkJ = b.blk, work2J = work2, k = i, blkK = blkI,
+ borrowIn = false; j < b.len; j++, bBlkJ++, work2J++, k++, blkK++) {
+ temp = *blkK - ((*bBlkJ << i2) | bHigh);
+ borrowOut = (temp > *blkK);
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ *work2J = temp;
+ borrowIn = borrowOut;
+ bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2);
+ }
+ temp = *blkK - bHigh;
+ borrowOut = (temp > *blkK);
+ if (borrowIn) {
+ borrowOut |= (temp == 0);
+ temp--;
+ }
+ *work2J = temp;
+ borrowIn = borrowOut;
+ j++;
+ work2J++;
+ k++;
+ blkK++;
+ for (; k < a.len + 1 && borrowIn; j++, work2J++, k++, blkK++) {
+ borrowIn = (*blkK == 0);
+ *work2J = *blkK - 1;
+ }
+ // If the subtraction was performed successfully, set bit i2
+ // in block i of the quotient, and copy the changed portion of
+ // work2 back to this.
+ if (!borrowIn)
+ while (j > 0) {
+ j--;
+ work2J--;
+ k--;
+ blkK--;
+ *blkK = *work2J;
+ }
+ }
+ }
+ // Blocks higher than the last block of the modulus are zero.
+ len = b.len;
+ // Zap leading zeros
+ zapLeadingZeros();
+}
+
+// Bitwise and
+void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::bitAnd: One of the arguments is the invoked object";
+ len = (a.len >= b.len) ? b.len : a.len;
+ allocate(len);
+ BlkNum i;
+ Blk *blkI;
+ const Blk *aBlkI, *bBlkI;
+ for (i = 0, blkI = blk, aBlkI = a.blk, bBlkI = b.blk;
+ i < len; i++, blkI++, aBlkI++, bBlkI++)
+ *blkI = *aBlkI & *bBlkI;
+ zapLeadingZeros();
+}
+
+// Bitwise or
+void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::bitOr: One of the arguments is the invoked object";
+ BlkNum i;
+ Blk *blkI;
+ const BigUnsigned *a2, *b2;
+ if (a.len >= b.len) {
+ a2 = &a;
+ b2 = &b;
+ } else {
+ a2 = &b;
+ b2 = &a;
+ }
+ allocate(a2->len);
+ const Blk *a2BlkI, *b2BlkI;
+ for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk;
+ i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++)
+ *blkI = *a2BlkI | *b2BlkI;
+ for (; i < a2->len; i++, blkI++, a2BlkI++)
+ *blkI = *a2BlkI;
+ len = a2->len;
+}
+
+// Bitwise xor
+void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
+ // Block unsafe calls
+ if (this == &a || this == &b)
+ throw "BigUnsigned::bitXor: One of the arguments is the invoked object";
+ BlkNum i;
+ Blk *blkI;
+ const BigUnsigned *a2, *b2;
+ if (a.len >= b.len) {
+ a2 = &a;
+ b2 = &b;
+ } else {
+ a2 = &b;
+ b2 = &a;
+ }
+ allocate(b2->len);
+ const Blk *a2BlkI, *b2BlkI;
+ for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk;
+ i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++)
+ *blkI = *a2BlkI ^ *b2BlkI;
+ for (; i < a2->len; i++, blkI++, a2BlkI++)
+ *blkI = *a2BlkI;
+ len = a2->len;
+ zapLeadingZeros();
+}
+
+// INCREMENT/DECREMENT OPERATORS
+
+// Prefix increment
+void BigUnsigned::operator ++() {
+ BlkNum i;
+ Blk *blkI;
+ bool carry = true;
+ for (i = 0, blkI = blk; i < len && carry; i++) {
+ (*blkI)++;
+ carry = (*blkI == 0);
+ }
+ if (carry) {
+ allocateAndCopy(len + 1);
+ *blkI = 1;
+ }
+}
+
+// Postfix increment: same as prefix
+void BigUnsigned::operator ++(int) {
+ operator ++();
+}
+
+// Prefix decrement
+void BigUnsigned::operator --() {
+ if (len == 0)
+ throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
+ BlkNum i;
+ Blk *blkI;
+ bool borrow = true;
+ for (i = 0, blkI = blk; borrow; i++) {
+ borrow = (*blkI == 0);
+ (*blkI)--;
+ }
+ if (blk[len - 1] == 0)
+ len--;
+}
+
+// Postfix decrement: same as prefix
+void BigUnsigned::operator --(int) {
+ operator --();
+}
+