From: Matt McCutchen Date: Thu, 14 Jun 2007 20:24:26 +0000 (-0400) Subject: Version 2007.06.14: X-Git-Tag: v2007.07.07~1 X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/commitdiff_plain/ef2b7c5922c36f93923dd3482c5bfd41b14d82ce Version 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. --- diff --git a/BigUnsigned.cc b/BigUnsigned.cc index a68b8ac..3c9a1d7 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -225,7 +225,7 @@ BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { * 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 @@ -238,7 +238,7 @@ BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { * 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; \ @@ -248,7 +248,7 @@ BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { // 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); @@ -309,7 +309,7 @@ void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &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); @@ -421,7 +421,7 @@ inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num, // 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; @@ -723,7 +723,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { // 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; @@ -734,7 +734,7 @@ void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) { // 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) { @@ -754,7 +754,7 @@ void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { // 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) { @@ -773,6 +773,51 @@ void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { 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 diff --git a/BigUnsigned.hh b/BigUnsigned.hh index 1eb056f..61fcb90 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -184,16 +184,14 @@ class BigUnsigned : protected NumberlikeArray { // 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) @@ -207,6 +205,11 @@ class BigUnsigned : protected NumberlikeArray { 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. @@ -219,6 +222,11 @@ class BigUnsigned : protected NumberlikeArray { 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, @@ -277,6 +285,26 @@ inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { 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 @@ -319,5 +347,21 @@ inline void BigUnsigned::operator |=(const BigUnsigned &x) { 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 diff --git a/ChangeLog b/ChangeLog index e53260c..133ddae 100644 --- a/ChangeLog +++ b/ChangeLog @@ -6,6 +6,12 @@ roughly corresponds to the release date of that version in `YYYY.MM.DD[.N]' 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. diff --git a/Makefile b/Makefile index ab917ec..db8cb4f 100644 --- a/Makefile +++ b/Makefile @@ -7,7 +7,7 @@ all : # 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 diff --git a/sample.cc b/sample.cc index a560e6b..f60a294 100644 --- a/sample.cc +++ b/sample.cc @@ -62,10 +62,17 @@ int main() { * ``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);