1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697
|
#include "BigUnsigned.hh"
// Memory management definitions have moved to the bottom of NumberlikeArray.hh.
// 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); }
BigUnsigned::BigUnsigned(unsigned short x) { initFromPrimitive (x); }
BigUnsigned::BigUnsigned( long x) { initFromSignedPrimitive(x); }
BigUnsigned::BigUnsigned( int x) { initFromSignedPrimitive(x); }
BigUnsigned::BigUnsigned( short x) { initFromSignedPrimitive(x); }
unsigned long BigUnsigned::toUnsignedLong () const { return convertToPrimitive <unsigned long >(); }
unsigned int BigUnsigned::toUnsignedInt () const { return convertToPrimitive <unsigned int >(); }
unsigned short BigUnsigned::toUnsignedShort() const { return convertToPrimitive <unsigned short>(); }
long BigUnsigned::toLong () const { return convertToSignedPrimitive< long >(); }
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 = Blk(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.
if (len < x.len)
return less;
else if (len > x.len)
return greater;
else {
// Compare blocks one by one from left to right.
Index i = len;
while (i > 0) {
i--;
if (blk[i] == x.blk[i])
continue;
else if (blk[i] > x.blk[i])
return greater;
else
return less;
}
// If no blocks differed, the numbers are equal.
return equal;
}
}
// COPY-LESS OPERATIONS
/*
* On most calls to copy-less operations, it's safe to read the inputs little by
* little and write the outputs little by little. However, if one of the
* inputs is coming from the same variable into which the output is to be
* 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 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
* BigUnsigned.hh). Before then, put-here operations rejected aliased calls
* with an exception. I think doing the right thing is better.
*
* Some of the put-here operations can probably handle aliased calls safely
* without the extra copy because (for example) they process blocks strictly
* right-to-left. At some point I might determine which ones don't need the
* copy, but my reasoning would need to be verified very carefully. For now
* I'll leave in the copy.
*/
#define DTRT_ALIASED(cond, op) \
if (cond) { \
BigUnsigned tmpThis; \
tmpThis.op; \
*this = tmpThis; \
return; \
}
void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, add(a, b));
// If one argument is zero, copy the other.
if (a.len == 0) {
operator =(b);
return;
} else if (b.len == 0) {
operator =(a);
return;
}
// Some variables...
// Carries in and out of an addition stage
bool carryIn, carryOut;
Blk temp;
Index 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;
}
// 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, carryIn = false; i < b2->len; i++) {
// Add input blocks
temp = a2->blk[i] + b2->blk[i];
// If a rollover occurred, the result is less than either input.
// This test is used many times in the BigUnsigned code.
carryOut = (temp < a2->blk[i]);
// If a carry was input, handle it
if (carryIn) {
temp++;
carryOut |= (temp == 0);
}
blk[i] = 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++) {
temp = a2->blk[i] + 1;
carryIn = (temp == 0);
blk[i] = temp;
}
// If the carry was resolved but the larger number
// still has blocks, copy them over.
for (; i < a2->len; i++)
blk[i] = a2->blk[i];
// Set the extra block if there's still a carry, decrease length otherwise
if (carryIn)
blk[i] = 1;
else
len--;
}
void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
if (b.len == 0) {
// If b is zero, copy a.
operator =(a);
return;
} else if (a.len < b.len)
// If a is shorter than b, the result is negative.
throw "BigUnsigned::subtract: "
"Negative result in unsigned calculation";
// Some variables...
bool borrowIn, borrowOut;
Blk temp;
Index i;
// Set preliminary length and make room
len = a.len;
allocate(len);
// For each block index that is present in both inputs...
for (i = 0, borrowIn = false; i < b.len; i++) {
temp = a.blk[i] - b.blk[i];
// If a reverse rollover occurred,
// the result is greater than the block from a.
borrowOut = (temp > a.blk[i]);
// Handle an incoming borrow
if (borrowIn) {
borrowOut |= (temp == 0);
temp--;
}
blk[i] = 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++) {
borrowIn = (a.blk[i] == 0);
blk[i] = a.blk[i] - 1;
}
/* If there's still a borrow, the result is negative.
* Throw an exception, but zero out this object so as to leave it in a
* predictable state. */
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++)
blk[i] = a.blk[i];
// Zap leading zeros
zapLeadingZeros();
}
/*
* About the multiplication and division algorithms:
*
* I searched unsucessfully for fast C++ built-in operations like the `b_0'
* and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
* Programming'' (replace `place' by `Blk'):
*
* ``b_0[:] multiplication of a one-place integer by another one-place
* integer, giving a two-place answer;
*
* ``c_0[:] division of a two-place integer by a one-place integer,
* provided that the quotient is a one-place integer, and yielding
* also a one-place remainder.''
*
* I also missed his note that ``[b]y adjusting the word size, if
* necessary, nearly all computers will have these three operations
* available'', so I gave up on trying to use algorithms similar to his.
* A future version of the library might include such algorithms; I
* would welcome contributions from others for this.
*
* I eventually decided to use bit-shifting algorithms. To multiply `a'
* and `b', we zero out the result. Then, for each `1' bit in `a', we
* shift `b' left the appropriate amount and add it to the result.
* Similarly, to divide `a' by `b', we shift `b' left varying amounts,
* repeatedly trying to subtract it from `a'. When we succeed, we note
* the fact by setting a bit in the quotient. While these algorithms
* have the same O(n^2) time complexity as Knuth's, the ``constant factor''
* is likely to be larger.
*
* Because I used these algorithms, which require single-block addition
* and subtraction rather than single-block multiplication and division,
* the innermost loops of all four routines are very similar. Study one
* of them and all will become clear.
*/
/*
* This is a little inline function used by both the multiplication
* routine and the division routine.
*
* `getShiftedBlock' returns the `x'th block of `num << y'.
* `y' may be anything from 0 to N - 1, and `x' may be anything from
* 0 to `num.len'.
*
* Two things contribute to this block:
*
* (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
*
* (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
*
* But we must be careful if `x == 0' or `x == num.len', in
* which case we should use 0 instead of (2) or (1), respectively.
*
* If `y == 0', then (2) contributes 0, as it should. However,
* in some computer environments, for a reason I cannot understand,
* `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
* will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
* the test `y == 0' handles this case specially.
*/
inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
BigUnsigned::Index x, unsigned int y) {
BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
return part1 | part2;
}
void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &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;
return;
}
/*
* Overall method:
*
* Set this = 0.
* For each 1-bit of `a' (say the `i2'th bit of block `i'):
* Add `b << (i blocks and i2 bits)' to *this.
*/
// Variables for the calculation
Index i, j, k;
unsigned int i2;
Blk temp;
bool carryIn, carryOut;
// Set preliminary length and make room
len = a.len + b.len;
allocate(len);
// Zero out this object
for (i = 0; i < len; i++)
blk[i] = 0;
// For each block of the first number...
for (i = 0; i < a.len; i++) {
// For each 1-bit of that block...
for (i2 = 0; i2 < N; i2++) {
if ((a.blk[i] & (Blk(1) << i2)) == 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.
*
* `getShiftedBlock', a short inline function defined above,
* is now used for the bit handling. It replaces the more
* complex `bHigh' code, in which each run of the loop dealt
* immediately with the low bits and saved the high bits to
* be picked up next time. The last run of the loop used to
* leave leftover high bits, which were handled separately.
* Instead, this loop runs an additional time with j == b.len.
* These changes were made on 2005.01.11.
*/
for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
/*
* The body of this loop is very similar to the body of the first loop
* in `add', except that this loop does a `+=' instead of a `+'.
*/
temp = blk[k] + getShiftedBlock(b, j, i2);
carryOut = (temp < blk[k]);
if (carryIn) {
temp++;
carryOut |= (temp == 0);
}
blk[k] = temp;
carryIn = carryOut;
}
// No more extra iteration to deal with `bHigh'.
// Roll-over a carry as necessary.
for (; carryIn; k++) {
blk[k]++;
carryIn = (blk[k] == 0);
}
}
}
// Zap possible leading zero
if (blk[len - 1] == 0)
len--;
}
/*
* DIVISION WITH REMAINDER
* This monstrous function mods *this by the given divisor b while storing the
* quotient in the given object q; at the end, *this contains the remainder.
* The seemingly bizarre pattern of inputs and outputs was chosen so that the
* function copies as little as possible (since it is implemented by repeated
* subtraction of multiples of b from *this).
*
* "modWithQuotient" might be a better name for this function, but I would
* rather not change the name now.
*/
void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
/* Defending against aliased calls is more complex than usual because we
* are writing to both *this and q.
*
* It would be silly to try to write quotient and remainder to the
* same variable. Rule that out right away. */
if (this == &q)
throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable";
/* Now *this and q are separate, so the only concern is that b might be
* aliased to one of them. If so, use a temporary copy of b. */
if (this == &b || &q == &b) {
BigUnsigned tmpB(b);
divideWithRemainder(tmpB, q);
return;
}
/*
* Knuth's definition of mod (which this function uses) is somewhat
* different from the C++ definition of % in case of division by 0.
*
* We let a / 0 == 0 (it doesn't matter much) and a % 0 == a, no
* exceptions thrown. This allows us to preserve both Knuth's demand
* that a mod 0 == a and the useful property that
* (a / b) * b + (a % b) == a.
*/
if (b.len == 0) {
q.len = 0;
return;
}
/*
* If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
* *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
*/
if (len < b.len) {
q.len = 0;
return;
}
// At this point we know (*this).len >= b.len > 0. (Whew!)
/*
* Overall method:
*
* For each appropriate i and i2, decreasing:
* Subtract (b << (i blocks and i2 bits)) from *this, storing the
* result in subtractBuf.
* If the subtraction succeeds with a nonnegative result:
* Turn on bit i2 of block i of the quotient q.
* Copy subtractBuf back into *this.
* Otherwise bit i2 of block i remains off, and *this is unchanged.
*
* Eventually q will contain the entire quotient, and *this will
* be left with the remainder.
*
* subtractBuf[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
* But on a single iteration, we don't touch the i lowest blocks of blk
* (and don't use those of subtractBuf) because these blocks are
* unaffected by the subtraction: we are subtracting
* (b << (i blocks and i2 bits)), which ends in at least `i' zero
* blocks. */
// Variables for the calculation
Index i, j, k;
unsigned int i2;
Blk temp;
bool borrowIn, borrowOut;
/*
* Make sure we have an extra zero block just past the value.
*
* When we attempt a subtraction, we might shift `b' so
* its first block begins a few bits left of the dividend,
* and then we'll try to compare these extra bits with
* a nonexistent block to the left of the dividend. The
* extra zero block ensures sensible behavior; we need
* an extra block in `subtractBuf' for exactly the same reason.
*/
Index origLen = len; // Save real length.
/* To avoid an out-of-bounds access in case of reallocation, allocate
* first and then increment the logical length. */
allocateAndCopy(len + 1);
len++;
blk[origLen] = 0; // Zero the added block.
// subtractBuf holds part of the result of a subtraction; see above.
Blk *subtractBuf = new Blk[len];
// Set preliminary length for quotient and make room
q.len = origLen - b.len + 1;
q.allocate(q.len);
// Zero out the quotient
for (i = 0; i < q.len; i++)
q.blk[i] = 0;
// For each possible left-shift of b in blocks...
i = q.len;
while (i > 0) {
i--;
// For each possible left-shift of b in bits...
// (Remember, N is the number of bits in a Blk.)
q.blk[i] = 0;
i2 = N;
while (i2 > 0) {
i2--;
/*
* Subtract b, shifted left i blocks and i2 bits, from *this,
* and store the answer in subtractBuf. In the for loop, `k == i + j'.
*
* Compare this to the middle section of `multiply'. They
* are in many ways analogous. See especially the discussion
* of `getShiftedBlock'.
*/
for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
temp = blk[k] - getShiftedBlock(b, j, i2);
borrowOut = (temp > blk[k]);
if (borrowIn) {
borrowOut |= (temp == 0);
temp--;
}
// Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'.
subtractBuf[k] = temp;
borrowIn = borrowOut;
}
// No more extra iteration to deal with `bHigh'.
// Roll-over a borrow as necessary.
for (; k < origLen && borrowIn; k++) {
borrowIn = (blk[k] == 0);
subtractBuf[k] = blk[k] - 1;
}
/*
* If the subtraction was performed successfully (!borrowIn),
* set bit i2 in block i of the quotient.
*
* Then, copy the portion of subtractBuf filled by the subtraction
* back to *this. This portion starts with block i and ends--
* where? Not necessarily at block `i + b.len'! Well, we
* increased k every time we saved a block into subtractBuf, so
* the region of subtractBuf we copy is just [i, k).
*/
if (!borrowIn) {
q.blk[i] |= (Blk(1) << i2);
while (k > i) {
k--;
blk[k] = subtractBuf[k];
}
}
}
}
// Zap possible leading zero in quotient
if (q.blk[q.len - 1] == 0)
q.len--;
// Zap any/all leading zeros in remainder
zapLeadingZeros();
// Deallocate subtractBuf.
// (Thanks to Brad Spencer for noticing my accidental omission of this!)
delete [] subtractBuf;
}
/* BITWISE OPERATORS
* These are straightforward blockwise operations except that they differ in
* the output length and the necessity of zapLeadingZeros. */
void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b));
// The bitwise & can't be longer than either operand.
len = (a.len >= b.len) ? b.len : a.len;
allocate(len);
Index i;
for (i = 0; i < len; i++)
blk[i] = a.blk[i] & b.blk[i];
zapLeadingZeros();
}
void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
Index i;
const BigUnsigned *a2, *b2;
if (a.len >= b.len) {
a2 = &a;
b2 = &b;
} else {
a2 = &b;
b2 = &a;
}
allocate(a2->len);
for (i = 0; i < b2->len; i++)
blk[i] = a2->blk[i] | b2->blk[i];
for (; i < a2->len; i++)
blk[i] = a2->blk[i];
len = a2->len;
// Doesn't need zapLeadingZeros.
}
void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
Index i;
const BigUnsigned *a2, *b2;
if (a.len >= b.len) {
a2 = &a;
b2 = &b;
} else {
a2 = &b;
b2 = &a;
}
allocate(a2->len);
for (i = 0; i < b2->len; i++)
blk[i] = a2->blk[i] ^ b2->blk[i];
for (; i < a2->len; i++)
blk[i] = a2->blk[i];
len = a2->len;
zapLeadingZeros();
}
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
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--;
}
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;
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
void BigUnsigned::operator ++() {
Index i;
bool carry = true;
for (i = 0; i < len && carry; i++) {
blk[i]++;
carry = (blk[i] == 0);
}
if (carry) {
// Allocate and then increase length, as in divideWithRemainder
allocateAndCopy(len + 1);
len++;
blk[i] = 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";
Index i;
bool borrow = true;
for (i = 0; borrow; i++) {
borrow = (blk[i] == 0);
blk[i]--;
}
// Zap possible leading zero (there can only be one)
if (blk[len - 1] == 0)
len--;
}
// Postfix decrement: same as prefix
void BigUnsigned::operator --(int) {
operator --();
}
|