From: Matt McCutchen <matt@mattmccutchen.net>
Date: Wed, 16 Jul 2008 20:51:27 +0000 (-0400)
Subject: Add BigUnsigned functions setBlock, bitLength, getBit, setBit with tests.
X-Git-Tag: v2008.07.20~10
X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/commitdiff_plain/88dbe518aa4ac1489b0d2387288c1f922fc5ea61

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

diff --git a/BigUnsigned.cc b/BigUnsigned.cc
index a4e6d9b..ffb6c6c 100644
--- 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
--- 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
--- 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