X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/3e1327901d299a537a8d932c49dd330f87ac3bda..c17afa550d0a00498301454195699120e2bf58c5:/BigUnsigned.cc diff --git a/BigUnsigned.cc b/BigUnsigned.cc index db407c5..d7f9889 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -2,38 +2,8 @@ // Memory management definitions have moved to the bottom of NumberlikeArray.hh. -// CONSTRUCTION FROM PRIMITIVE INTEGERS - -/* Initialize this BigUnsigned from the given primitive integer. The same - * pattern works for all primitive integer types, so I put it into a template to - * reduce code duplication. (Don't worry: this is protected and we instantiate - * it only with primitive integer types.) Type X could be signed, but x is - * known to be nonnegative. */ -template -void BigUnsigned::initFromPrimitive(X x) { - if (x == 0) - ; // NumberlikeArray already initialized us to zero. - else { - // Create a single block. blk is NULL; no need to delete it. - cap = 1; - blk = new Blk[1]; - len = 1; - blk[0] = Blk(x); - } -} - -/* Ditto, but first check that x is nonnegative. I could have put the check in - * initFromPrimitive and let the compiler optimize it out for unsigned-type - * instantiations, but I wanted to avoid the warning stupidly issued by g++ for - * a condition that is constant in *any* instantiation, even if not in all. */ -template -void BigUnsigned::initFromSignedPrimitive(X x) { - if (x < 0) - throw "BigUnsigned constructor: " - "Cannot construct a BigUnsigned from a negative number"; - else - initFromPrimitive(x); -} +// The templates used by these constructors and converters are at the bottom of +// BigUnsigned.hh. BigUnsigned::BigUnsigned(unsigned long x) { initFromPrimitive (x); } BigUnsigned::BigUnsigned(unsigned int x) { initFromPrimitive (x); } @@ -42,60 +12,57 @@ BigUnsigned::BigUnsigned( long x) { initFromSignedPrimitive(x); } BigUnsigned::BigUnsigned( int x) { initFromSignedPrimitive(x); } BigUnsigned::BigUnsigned( short x) { initFromSignedPrimitive(x); } -// CONVERSION TO PRIMITIVE INTEGERS +unsigned long BigUnsigned::toUnsignedLong () const { return convertToPrimitive (); } +unsigned int BigUnsigned::toUnsignedInt () const { return convertToPrimitive (); } +unsigned short BigUnsigned::toUnsignedShort() const { return convertToPrimitive (); } +long BigUnsigned::toLong () const { return convertToSignedPrimitive< long >(); } +int BigUnsigned::toInt () const { return convertToSignedPrimitive< int >(); } +short BigUnsigned::toShort () const { return convertToSignedPrimitive< short>(); } -/* Template with the same idea as initFromPrimitive. This might be slightly - * slower than the previous version with the masks, but it's much shorter and - * clearer, which is the library's stated goal. */ -template -X BigUnsigned::convertToPrimitive() const { - if (len == 0) - // The number is zero; return zero. - return 0; - else if (len == 1) { - // The single block might fit in an X. Try the conversion. - X x = X(blk[0]); - // Make sure the result accurately represents the block. - if (Blk(x) == blk[0]) - // Successful conversion. - return x; - // Otherwise fall through. +// BIT/BLOCK ACCESSORS + +void BigUnsigned::setBlock(Index i, Blk newBlock) { + if (newBlock == 0) { + if (i < len) { + blk[i] = 0; + zapLeadingZeros(); + } + // If i >= len, no effect. + } else { + if (i >= len) { + // The nonzero block extends the number. + allocateAndCopy(i+1); + // Zero any added blocks that we aren't setting. + for (Index j = len; j < i; j++) + blk[j] = 0; + len = i+1; + } + blk[i] = newBlock; } - throw "BigUnsigned::to: " - "Value is too big to fit in the requested type"; } -/* Wrap the above in an x >= 0 test to make sure we got a nonnegative result, - * not a negative one that happened to convert back into the correct nonnegative - * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again, - * separated to avoid a g++ warning. */ -template -X BigUnsigned::convertToSignedPrimitive() const { - X x = convertToPrimitive(); - if (x >= 0) - return x; - else - throw "BigUnsigned::to(Primitive): " - "Value is too big to fit in the requested type"; +/* Evidently the compiler wants BigUnsigned:: on the return type because, at + * that point, it hasn't yet parsed the BigUnsigned:: on the name to get the + * proper scope. */ +BigUnsigned::Index BigUnsigned::bitLength() const { + if (isZero()) + return 0; + else { + Blk leftmostBlock = getBlock(len - 1); + Index leftmostBlockLen = 0; + while (leftmostBlock != 0) { + leftmostBlock >>= 1; + leftmostBlockLen++; + } + return leftmostBlockLen + (len - 1) * N; + } } -unsigned long BigUnsigned::toUnsignedLong() const { - return convertToPrimitive(); -} -unsigned int BigUnsigned::toUnsignedInt() const { - return convertToPrimitive(); -} -unsigned short BigUnsigned::toUnsignedShort() const { - return convertToPrimitive(); -} -long BigUnsigned::toLong() const { - return convertToSignedPrimitive(); -} -int BigUnsigned::toInt() const { - return convertToSignedPrimitive(); -} -short BigUnsigned::toShort() const { - return convertToSignedPrimitive(); +void BigUnsigned::setBit(Index bi, bool newBit) { + Index blockI = bi / N; + Blk block = getBlock(blockI), mask = Blk(1) << (bi % N); + block = newBit ? (block | mask) : (block & ~mask); + setBlock(blockI, block); } // COMPARISON @@ -625,8 +592,17 @@ void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { zapLeadingZeros(); } -void BigUnsigned::bitShiftLeft(const BigUnsigned &a, unsigned int b) { +void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { DTRT_ALIASED(this == &a, bitShiftLeft(a, b)); + if (b < 0) { + if (b << 1 == 0) + throw "BigUnsigned::bitShiftLeft: " + "Pathological shift amount not implemented"; + else { + bitShiftRight(a, -b); + return; + } + } Index shiftBlocks = b / N; unsigned int shiftBits = b % N; // + 1: room for high bits nudged left into another block @@ -642,8 +618,17 @@ void BigUnsigned::bitShiftLeft(const BigUnsigned &a, unsigned int b) { len--; } -void BigUnsigned::bitShiftRight(const BigUnsigned &a, unsigned int b) { +void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { DTRT_ALIASED(this == &a, bitShiftRight(a, b)); + if (b < 0) { + if (b << 1 == 0) + throw "BigUnsigned::bitShiftRight: " + "Pathological shift amount not implemented"; + else { + bitShiftLeft(a, -b); + return; + } + } // 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;