Add BigUnsigned functions setBlock, bitLength, getBit, setBit with tests.

diff --git a/BigUnsigned.cc b/BigUnsigned.cc
index a4e6d9b..ffb6c6c 100644 (file)
--- a/BigUnsigned.cc
+++ b/BigUnsigned.cc
@@ -19,6 +19,52 @@ long           BigUnsigned::toLong         () const { return convertToSignedPrim
 int            BigUnsigned::toInt          () const { return convertToSignedPrimitive<         int  >(); }
 short          BigUnsigned::toShort        () const { return convertToSignedPrimitive<         short>(); }
 
+// 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;
+       }
+}
+
+/* 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;
+       }
+}
+
+void BigUnsigned::setBit(Index bi, bool newBit) {
+       Index blockI = bi / N;
+       Blk block = getBlock(blockI), mask = 1 << (bi % N);
+       block = newBit ? (block | mask) : (block & ~mask);
+       setBlock(blockI, block);
+}
+
 // COMPARISON
 BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
        // A bigger length implies a bigger number.

diff --git a/BigUnsigned.hh b/BigUnsigned.hh
index 0813234..f5267bb 100644 (file)
--- a/BigUnsigned.hh
+++ b/BigUnsigned.hh
@@ -81,7 +81,7 @@ protected:
        template <class X> X convertToPrimitive      () const;
 public:
 
-       // ACCESSORS
+       // BIT/BLOCK ACCESSORS
 
        // Expose these from NumberlikeArray directly.
        NumberlikeArray<Blk>::getCapacity;
@@ -90,10 +90,21 @@ public:
        /* Returns the requested block, or 0 if it is beyond the length (as if
         * the number had 0s infinitely to the left). */
        Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; }
+       void setBlock(Index i, Blk newBlock);
 
        // The number is zero if and only if the canonical length is zero.
        bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); }
 
+       /* Returns the length of the number in bits, i.e., zero if the number
+        * is zero and otherwise one more than the largest value of bi for
+        * which getBit(bi) returns true. */
+       Index bitLength() const;
+       // Get or set bit number bi, which has value 2^bi.
+       bool getBit(Index bi) const {
+               return (getBlock(bi / N) & (1 << (bi % N))) != 0;
+       }
+       void setBit(Index bi, bool newBit);
+
        // COMPARISONS
 
        // Compares this to x like Perl's <=>

diff --git a/testsuite.cc b/testsuite.cc
index a831fbc..9fab02a 100644 (file)
--- a/testsuite.cc
+++ b/testsuite.cc
@@ -165,6 +165,56 @@ TEST(a % 123); //81
 
 TEST(BigUnsigned(5) / 0); //error
 
+// Block accessors
+BigUnsigned b;
+TEST(b); //0
+TEST(b.getBlock(0)); //0
+b.setBlock(1, 314);
+// Did b grow properly?  And did we zero intermediate blocks?
+TEST(check(b)); //1348619730944
+TEST(b.getLength()); //2
+TEST(b.getBlock(0)); //0
+TEST(b.getBlock(1)); //314
+// Did b shrink properly?
+b.setBlock(1, 0);
+TEST(check(b)); //0
+
+BigUnsigned bb(314);
+bb.setBlock(1, 159);
+// Make sure we used allocateAndCopy, not allocate
+TEST(bb.getBlock(0)); //314
+TEST(bb.getBlock(1)); //159
+// Blocks beyond the number should be zero regardless of whether they are
+// within the capacity.
+bb.add(1, 2);
+TEST(bb.getBlock(0)); //3
+TEST(bb.getBlock(1)); //0
+TEST(bb.getBlock(2)); //0
+TEST(bb.getBlock(314159)); //0
+
+// Bit accessors
+TEST(BigUnsigned(0).bitLength()); //0
+TEST(BigUnsigned(1).bitLength()); //1
+TEST(BigUnsigned(4095).bitLength()); //12
+TEST(BigUnsigned(4096).bitLength()); //13
+// 5 billion is between 2^32 (about 4 billion) and 2^33 (about 8 billion).
+TEST(stringToBigUnsigned("5000000000").bitLength()); //33
+
+// 25 is binary 11001.
+BigUnsigned bbb(25);
+TEST(bbb.getBit(4)); //1
+TEST(bbb.getBit(3)); //1
+TEST(bbb.getBit(2)); //0
+TEST(bbb.getBit(1)); //0
+TEST(bbb.getBit(0)); //1
+TEST(bbb.bitLength()); //5
+// Effectively add 2^32.
+bbb.setBit(32, true);
+TEST(bbb); //4294967321
+bbb.setBit(31, true);
+bbb.setBit(32, false);
+TEST(check(bbb)); //2147483673
+
 BigUnsigned p1 = BigUnsigned(3) * 5;
 TEST(p1); //15
 /* In this case, we would like g++ to implicitly promote the BigUnsigned to a