1
// Copyright 2009 The Closure Library Authors. All Rights Reserved.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS-IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
/**
16
 * @fileoverview Defines an Integer class for representing (potentially)
17
 * infinite length two's-complement integer values.
18
 *
19
 * For the specific case of 64-bit integers, use goog.math.Long, which is more
20
 * efficient.
21
 *
22
 */
23

24
goog.provide('goog.math.Integer');
25

26

27

28
/**
29
 * Constructs a two's-complement integer an array containing bits of the
30
 * integer in 32-bit (signed) pieces, given in little-endian order (i.e.,
31
 * lowest-order bits in the first piece), and the sign of -1 or 0.
32
 *
33
 * See the from* functions below for other convenient ways of constructing
34
 * Integers.
35
 *
36
 * The internal representation of an integer is an array of 32-bit signed
37
 * pieces, along with a sign (0 or -1) that indicates the contents of all the
38
 * other 32-bit pieces out to infinity.  We use 32-bit pieces because these are
39
 * the size of integers on which Javascript performs bit-operations.  For
40
 * operations like addition and multiplication, we split each number into 16-bit
41
 * pieces, which can easily be multiplied within Javascript's floating-point
42
 * representation without overflow or change in sign.
43
 *
44
 * @struct
45
 * @constructor
46
 * @param {Array<number>} bits Array containing the bits of the number.
47
 * @param {number} sign The sign of the number: -1 for negative and 0 positive.
48
 * @final
49
 */
50
goog.math.Integer = function(bits, sign) {
51
  /**
52
   * @type {!Array<number>}
53
   * @private
54
   */
55
  this.bits_ = [];
56

57
  /**
58
   * @type {number}
59
   * @private
60
   */
61
  this.sign_ = sign;
62

63
  // Copy the 32-bit signed integer values passed in.  We prune out those at the
64
  // top that equal the sign since they are redundant.
65
  var top = true;
66
  for (var i = bits.length - 1; i >= 0; i--) {
67
    var val = bits[i] | 0;
68
    if (!top || val != sign) {
69
      this.bits_[i] = val;
70
      top = false;
71
    }
72
  }
73
};
74

75

76
// NOTE: Common constant values ZERO, ONE, NEG_ONE, etc. are defined below the
77
// from* methods on which they depend.
78

79

80
/**
81
 * A cache of the Integer representations of small integer values.
82
 * @type {!Object}
83
 * @private
84
 */
85
goog.math.Integer.IntCache_ = {};
86

87

88
/**
89
 * Returns an Integer representing the given (32-bit) integer value.
90
 * @param {number} value A 32-bit integer value.
91
 * @return {!goog.math.Integer} The corresponding Integer value.
92
 */
93
goog.math.Integer.fromInt = function(value) {
94
  if (-128 <= value && value < 128) {
95
    var cachedObj = goog.math.Integer.IntCache_[value];
96
    if (cachedObj) {
97
      return cachedObj;
98
    }
99
  }
100

101
  var obj = new goog.math.Integer([value | 0], value < 0 ? -1 : 0);
102
  if (-128 <= value && value < 128) {
103
    goog.math.Integer.IntCache_[value] = obj;
104
  }
105
  return obj;
106
};
107

108

109
/**
110
 * Returns an Integer representing the given value, provided that it is a finite
111
 * number.  Otherwise, zero is returned.
112
 * @param {number} value The value in question.
113
 * @return {!goog.math.Integer} The corresponding Integer value.
114
 */
115
goog.math.Integer.fromNumber = function(value) {
116
  if (isNaN(value) || !isFinite(value)) {
117
    return goog.math.Integer.ZERO;
118
  } else if (value < 0) {
119
    return goog.math.Integer.fromNumber(-value).negate();
120
  } else {
121
    var bits = [];
122
    var pow = 1;
123
    for (var i = 0; value >= pow; i++) {
124
      bits[i] = (value / pow) | 0;
125
      pow *= goog.math.Integer.TWO_PWR_32_DBL_;
126
    }
127
    return new goog.math.Integer(bits, 0);
128
  }
129
};
130

131

132
/**
133
 * Returns a Integer representing the value that comes by concatenating the
134
 * given entries, each is assumed to be 32 signed bits, given in little-endian
135
 * order (lowest order bits in the lowest index), and sign-extending the highest
136
 * order 32-bit value.
137
 * @param {Array<number>} bits The bits of the number, in 32-bit signed pieces,
138
 *     in little-endian order.
139
 * @return {!goog.math.Integer} The corresponding Integer value.
140
 */
141
goog.math.Integer.fromBits = function(bits) {
142
  var high = bits[bits.length - 1];
143
  return new goog.math.Integer(bits, high & (1 << 31) ? -1 : 0);
144
};
145

146

147
/**
148
 * Returns an Integer representation of the given string, written using the
149
 * given radix.
150
 * @param {string} str The textual representation of the Integer.
151
 * @param {number=} opt_radix The radix in which the text is written.
152
 * @return {!goog.math.Integer} The corresponding Integer value.
153
 */
154
goog.math.Integer.fromString = function(str, opt_radix) {
155
  if (str.length == 0) {
156
    throw Error('number format error: empty string');
157
  }
158

159
  var radix = opt_radix || 10;
160
  if (radix < 2 || 36 < radix) {
161
    throw Error('radix out of range: ' + radix);
162
  }
163

164
  if (str.charAt(0) == '-') {
165
    return goog.math.Integer.fromString(str.substring(1), radix).negate();
166
  } else if (str.indexOf('-') >= 0) {
167
    throw Error('number format error: interior "-" character');
168
  }
169

170
  // Do several (8) digits each time through the loop, so as to
171
  // minimize the calls to the very expensive emulated div.
172
  var radixToPower = goog.math.Integer.fromNumber(Math.pow(radix, 8));
173

174
  var result = goog.math.Integer.ZERO;
175
  for (var i = 0; i < str.length; i += 8) {
176
    var size = Math.min(8, str.length - i);
177
    var value = parseInt(str.substring(i, i + size), radix);
178
    if (size < 8) {
179
      var power = goog.math.Integer.fromNumber(Math.pow(radix, size));
180
      result = result.multiply(power).add(goog.math.Integer.fromNumber(value));
181
    } else {
182
      result = result.multiply(radixToPower);
183
      result = result.add(goog.math.Integer.fromNumber(value));
184
    }
185
  }
186
  return result;
187
};
188

189

190
/**
191
 * A number used repeatedly in calculations.  This must appear before the first
192
 * call to the from* functions below.
193
 * @type {number}
194
 * @private
195
 */
196
goog.math.Integer.TWO_PWR_32_DBL_ = (1 << 16) * (1 << 16);
197

198

199
/** @type {!goog.math.Integer} */
200
goog.math.Integer.ZERO = goog.math.Integer.fromInt(0);
201

202

203
/** @type {!goog.math.Integer} */
204
goog.math.Integer.ONE = goog.math.Integer.fromInt(1);
205

206

207
/**
208
 * @type {!goog.math.Integer}
209
 * @private
210
 */
211
goog.math.Integer.TWO_PWR_24_ = goog.math.Integer.fromInt(1 << 24);
212

213

214
/**
215
 * Returns the value, assuming it is a 32-bit integer.
216
 * @return {number} The corresponding int value.
217
 */
218
goog.math.Integer.prototype.toInt = function() {
219
  return this.bits_.length > 0 ? this.bits_[0] : this.sign_;
220
};
221

222

223
/** @return {number} The closest floating-point representation to this value. */
224
goog.math.Integer.prototype.toNumber = function() {
225
  if (this.isNegative()) {
226
    return -this.negate().toNumber();
227
  } else {
228
    var val = 0;
229
    var pow = 1;
230
    for (var i = 0; i < this.bits_.length; i++) {
231
      val += this.getBitsUnsigned(i) * pow;
232
      pow *= goog.math.Integer.TWO_PWR_32_DBL_;
233
    }
234
    return val;
235
  }
236
};
237

238

239
/**
240
 * @param {number=} opt_radix The radix in which the text should be written.
241
 * @return {string} The textual representation of this value.
242
 * @override
243
 */
244
goog.math.Integer.prototype.toString = function(opt_radix) {
245
  var radix = opt_radix || 10;
246
  if (radix < 2 || 36 < radix) {
247
    throw Error('radix out of range: ' + radix);
248
  }
249

250
  if (this.isZero()) {
251
    return '0';
252
  } else if (this.isNegative()) {
253
    return '-' + this.negate().toString(radix);
254
  }
255

256
  // Do several (6) digits each time through the loop, so as to
257
  // minimize the calls to the very expensive emulated div.
258
  var radixToPower = goog.math.Integer.fromNumber(Math.pow(radix, 6));
259

260
  var rem = this;
261
  var result = '';
262
  while (true) {
263
    var remDiv = rem.divide(radixToPower);
264
    // The right shifting fixes negative values in the case when
265
    // intval >= 2^31; for more details see
266
    // https://github.com/google/closure-library/pull/498
267
    var intval = rem.subtract(remDiv.multiply(radixToPower)).toInt() >>> 0;
268
    var digits = intval.toString(radix);
269

270
    rem = remDiv;
271
    if (rem.isZero()) {
272
      return digits + result;
273
    } else {
274
      while (digits.length < 6) {
275
        digits = '0' + digits;
276
      }
277
      result = '' + digits + result;
278
    }
279
  }
280
};
281

282

283
/**
284
 * Returns the index-th 32-bit (signed) piece of the Integer according to
285
 * little-endian order (i.e., index 0 contains the smallest bits).
286
 * @param {number} index The index in question.
287
 * @return {number} The requested 32-bits as a signed number.
288
 */
289
goog.math.Integer.prototype.getBits = function(index) {
290
  if (index < 0) {
291
    return 0;  // Allowing this simplifies bit shifting operations below...
292
  } else if (index < this.bits_.length) {
293
    return this.bits_[index];
294
  } else {
295
    return this.sign_;
296
  }
297
};
298

299

300
/**
301
 * Returns the index-th 32-bit piece as an unsigned number.
302
 * @param {number} index The index in question.
303
 * @return {number} The requested 32-bits as an unsigned number.
304
 */
305
goog.math.Integer.prototype.getBitsUnsigned = function(index) {
306
  var val = this.getBits(index);
307
  return val >= 0 ? val : goog.math.Integer.TWO_PWR_32_DBL_ + val;
308
};
309

310

311
/** @return {number} The sign bit of this number, -1 or 0. */
312
goog.math.Integer.prototype.getSign = function() {
313
  return this.sign_;
314
};
315

316

317
/** @return {boolean} Whether this value is zero. */
318
goog.math.Integer.prototype.isZero = function() {
319
  if (this.sign_ != 0) {
320
    return false;
321
  }
322
  for (var i = 0; i < this.bits_.length; i++) {
323
    if (this.bits_[i] != 0) {
324
      return false;
325
    }
326
  }
327
  return true;
328
};
329

330

331
/** @return {boolean} Whether this value is negative. */
332
goog.math.Integer.prototype.isNegative = function() {
333
  return this.sign_ == -1;
334
};
335

336

337
/** @return {boolean} Whether this value is odd. */
338
goog.math.Integer.prototype.isOdd = function() {
339
  return (this.bits_.length == 0) && (this.sign_ == -1) ||
340
      (this.bits_.length > 0) && ((this.bits_[0] & 1) != 0);
341
};
342

343

344
/**
345
 * @param {goog.math.Integer} other Integer to compare against.
346
 * @return {boolean} Whether this Integer equals the other.
347
 */
348
goog.math.Integer.prototype.equals = function(other) {
349
  if (this.sign_ != other.sign_) {
350
    return false;
351
  }
352
  var len = Math.max(this.bits_.length, other.bits_.length);
353
  for (var i = 0; i < len; i++) {
354
    if (this.getBits(i) != other.getBits(i)) {
355
      return false;
356
    }
357
  }
358
  return true;
359
};
360

361

362
/**
363
 * @param {goog.math.Integer} other Integer to compare against.
364
 * @return {boolean} Whether this Integer does not equal the other.
365
 */
366
goog.math.Integer.prototype.notEquals = function(other) {
367
  return !this.equals(other);
368
};
369

370

371
/**
372
 * @param {goog.math.Integer} other Integer to compare against.
373
 * @return {boolean} Whether this Integer is greater than the other.
374
 */
375
goog.math.Integer.prototype.greaterThan = function(other) {
376
  return this.compare(other) > 0;
377
};
378

379

380
/**
381
 * @param {goog.math.Integer} other Integer to compare against.
382
 * @return {boolean} Whether this Integer is greater than or equal to the other.
383
 */
384
goog.math.Integer.prototype.greaterThanOrEqual = function(other) {
385
  return this.compare(other) >= 0;
386
};
387

388

389
/**
390
 * @param {goog.math.Integer} other Integer to compare against.
391
 * @return {boolean} Whether this Integer is less than the other.
392
 */
393
goog.math.Integer.prototype.lessThan = function(other) {
394
  return this.compare(other) < 0;
395
};
396

397

398
/**
399
 * @param {goog.math.Integer} other Integer to compare against.
400
 * @return {boolean} Whether this Integer is less than or equal to the other.
401
 */
402
goog.math.Integer.prototype.lessThanOrEqual = function(other) {
403
  return this.compare(other) <= 0;
404
};
405

406

407
/**
408
 * Compares this Integer with the given one.
409
 * @param {goog.math.Integer} other Integer to compare against.
410
 * @return {number} 0 if they are the same, 1 if the this is greater, and -1
411
 *     if the given one is greater.
412
 */
413
goog.math.Integer.prototype.compare = function(other) {
414
  var diff = this.subtract(other);
415
  if (diff.isNegative()) {
416
    return -1;
417
  } else if (diff.isZero()) {
418
    return 0;
419
  } else {
420
    return +1;
421
  }
422
};
423

424

425
/**
426
 * Returns an integer with only the first numBits bits of this value, sign
427
 * extended from the final bit.
428
 * @param {number} numBits The number of bits by which to shift.
429
 * @return {!goog.math.Integer} The shorted integer value.
430
 */
431
goog.math.Integer.prototype.shorten = function(numBits) {
432
  var arr_index = (numBits - 1) >> 5;
433
  var bit_index = (numBits - 1) % 32;
434
  var bits = [];
435
  for (var i = 0; i < arr_index; i++) {
436
    bits[i] = this.getBits(i);
437
  }
438
  var sigBits = bit_index == 31 ? 0xFFFFFFFF : (1 << (bit_index + 1)) - 1;
439
  var val = this.getBits(arr_index) & sigBits;
440
  if (val & (1 << bit_index)) {
441
    val |= 0xFFFFFFFF - sigBits;
442
    bits[arr_index] = val;
443
    return new goog.math.Integer(bits, -1);
444
  } else {
445
    bits[arr_index] = val;
446
    return new goog.math.Integer(bits, 0);
447
  }
448
};
449

450

451
/** @return {!goog.math.Integer} The negation of this value. */
452
goog.math.Integer.prototype.negate = function() {
453
  return this.not().add(goog.math.Integer.ONE);
454
};
455

456

457
/**
458
 * Returns the sum of this and the given Integer.
459
 * @param {goog.math.Integer} other The Integer to add to this.
460
 * @return {!goog.math.Integer} The Integer result.
461
 */
462
goog.math.Integer.prototype.add = function(other) {
463
  var len = Math.max(this.bits_.length, other.bits_.length);
464
  var arr = [];
465
  var carry = 0;
466

467
  for (var i = 0; i <= len; i++) {
468
    var a1 = this.getBits(i) >>> 16;
469
    var a0 = this.getBits(i) & 0xFFFF;
470

471
    var b1 = other.getBits(i) >>> 16;
472
    var b0 = other.getBits(i) & 0xFFFF;
473

474
    var c0 = carry + a0 + b0;
475
    var c1 = (c0 >>> 16) + a1 + b1;
476
    carry = c1 >>> 16;
477
    c0 &= 0xFFFF;
478
    c1 &= 0xFFFF;
479
    arr[i] = (c1 << 16) | c0;
480
  }
481
  return goog.math.Integer.fromBits(arr);
482
};
483

484

485
/**
486
 * Returns the difference of this and the given Integer.
487
 * @param {goog.math.Integer} other The Integer to subtract from this.
488
 * @return {!goog.math.Integer} The Integer result.
489
 */
490
goog.math.Integer.prototype.subtract = function(other) {
491
  return this.add(other.negate());
492
};
493

494

495
/**
496
 * Returns the product of this and the given Integer.
497
 * @param {goog.math.Integer} other The Integer to multiply against this.
498
 * @return {!goog.math.Integer} The product of this and the other.
499
 */
500
goog.math.Integer.prototype.multiply = function(other) {
501
  if (this.isZero()) {
502
    return goog.math.Integer.ZERO;
503
  } else if (other.isZero()) {
504
    return goog.math.Integer.ZERO;
505
  }
506

507
  if (this.isNegative()) {
508
    if (other.isNegative()) {
509
      return this.negate().multiply(other.negate());
510
    } else {
511
      return this.negate().multiply(other).negate();
512
    }
513
  } else if (other.isNegative()) {
514
    return this.multiply(other.negate()).negate();
515
  }
516

517
  // If both numbers are small, use float multiplication
518
  if (this.lessThan(goog.math.Integer.TWO_PWR_24_) &&
519
      other.lessThan(goog.math.Integer.TWO_PWR_24_)) {
520
    return goog.math.Integer.fromNumber(this.toNumber() * other.toNumber());
521
  }
522

523
  // Fill in an array of 16-bit products.
524
  var len = this.bits_.length + other.bits_.length;
525
  var arr = [];
526
  for (var i = 0; i < 2 * len; i++) {
527
    arr[i] = 0;
528
  }
529
  for (var i = 0; i < this.bits_.length; i++) {
530
    for (var j = 0; j < other.bits_.length; j++) {
531
      var a1 = this.getBits(i) >>> 16;
532
      var a0 = this.getBits(i) & 0xFFFF;
533

534
      var b1 = other.getBits(j) >>> 16;
535
      var b0 = other.getBits(j) & 0xFFFF;
536

537
      arr[2 * i + 2 * j] += a0 * b0;
538
      goog.math.Integer.carry16_(arr, 2 * i + 2 * j);
539
      arr[2 * i + 2 * j + 1] += a1 * b0;
540
      goog.math.Integer.carry16_(arr, 2 * i + 2 * j + 1);
541
      arr[2 * i + 2 * j + 1] += a0 * b1;
542
      goog.math.Integer.carry16_(arr, 2 * i + 2 * j + 1);
543
      arr[2 * i + 2 * j + 2] += a1 * b1;
544
      goog.math.Integer.carry16_(arr, 2 * i + 2 * j + 2);
545
    }
546
  }
547

548
  // Combine the 16-bit values into 32-bit values.
549
  for (var i = 0; i < len; i++) {
550
    arr[i] = (arr[2 * i + 1] << 16) | arr[2 * i];
551
  }
552
  for (var i = len; i < 2 * len; i++) {
553
    arr[i] = 0;
554
  }
555
  return new goog.math.Integer(arr, 0);
556
};
557

558

559
/**
560
 * Carries any overflow from the given index into later entries.
561
 * @param {Array<number>} bits Array of 16-bit values in little-endian order.
562
 * @param {number} index The index in question.
563
 * @private
564
 */
565
goog.math.Integer.carry16_ = function(bits, index) {
566
  while ((bits[index] & 0xFFFF) != bits[index]) {
567
    bits[index + 1] += bits[index] >>> 16;
568
    bits[index] &= 0xFFFF;
569
    index++;
570
  }
571
};
572

573

574
/**
575
 * Returns "this" Integer divided by the given one. Both "this" and the given
576
 * Integer MUST be positive.
577
 *
578
 * This method is only needed for very large numbers (>10^308),
579
 * for which the original division algorithm gets into an infinite
580
 * loop (see https://github.com/google/closure-library/issues/500).
581
 *
582
 * The algorithm has some possible performance enhancements (or
583
 * could be rewritten entirely), it's just an initial solution for
584
 * the issue linked above.
585
 *
586
 * @param {!goog.math.Integer} other The Integer to divide "this" by.
587
 * @return {!goog.math.Integer} "this" value divided by the given one.
588
 * @private
589
 */
590
goog.math.Integer.prototype.slowDivide_ = function(other) {
591
  if (this.isNegative() || other.isNegative()) {
592
    throw Error('slowDivide_ only works with positive integers.');
593
  }
594

595
  var twoPower = goog.math.Integer.ONE;
596
  var multiple = other;
597

598
  // First we have to figure out what the highest bit of the result
599
  // is, so we increase "twoPower" and "multiple" until "multiple"
600
  // exceeds "this".
601
  while (multiple.lessThanOrEqual(this)) {
602
    twoPower = twoPower.shiftLeft(1);
603
    multiple = multiple.shiftLeft(1);
604
  }
605

606
  // Rewind by one power of two, giving us the highest bit of the
607
  // result.
608
  var res = twoPower.shiftRight(1);
609
  var total = multiple.shiftRight(1);
610

611
  // Now we starting decreasing "multiple" and "twoPower" to find the
612
  // rest of the bits of the result.
613
  var total2;
614
  multiple = multiple.shiftRight(2);
615
  twoPower = twoPower.shiftRight(2);
616
  while (!multiple.isZero()) {
617
    // whenever we can add "multiple" to the total and not exceed
618
    // "this", that means we've found a 1 bit. Else we've found a 0
619
    // and don't need to add to the result.
620
    total2 = total.add(multiple);
621
    if (total2.lessThanOrEqual(this)) {
622
      res = res.add(twoPower);
623
      total = total2;
624
    }
625
    multiple = multiple.shiftRight(1);
626
    twoPower = twoPower.shiftRight(1);
627
  }
628
  return res;
629
};
630

631

632
/**
633
 * Returns this Integer divided by the given one.
634
 * @param {!goog.math.Integer} other The Integer to divide this by.
635
 * @return {!goog.math.Integer} This value divided by the given one.
636
 */
637
goog.math.Integer.prototype.divide = function(other) {
638
  if (other.isZero()) {
639
    throw Error('division by zero');
640
  } else if (this.isZero()) {
641
    return goog.math.Integer.ZERO;
642
  }
643

644
  if (this.isNegative()) {
645
    if (other.isNegative()) {
646
      return this.negate().divide(other.negate());
647
    } else {
648
      return this.negate().divide(other).negate();
649
    }
650
  } else if (other.isNegative()) {
651
    return this.divide(other.negate()).negate();
652
  }
653

654
  // Have to degrade to slowDivide for Very Large Numbers, because
655
  // they're out of range for the floating-point approximation
656
  // technique used below.
657
  if (this.bits_.length > 30) {
658
    return this.slowDivide_(other);
659
  }
660

661
  // Repeat the following until the remainder is less than other:  find a
662
  // floating-point that approximates remainder / other *from below*, add this
663
  // into the result, and subtract it from the remainder.  It is critical that
664
  // the approximate value is less than or equal to the real value so that the
665
  // remainder never becomes negative.
666
  var res = goog.math.Integer.ZERO;
667
  var rem = this;
668
  while (rem.greaterThanOrEqual(other)) {
669
    // Approximate the result of division. This may be a little greater or
670
    // smaller than the actual value.
671
    var approx = Math.max(1, Math.floor(rem.toNumber() / other.toNumber()));
672

673
    // We will tweak the approximate result by changing it in the 48-th digit or
674
    // the smallest non-fractional digit, whichever is larger.
675
    var log2 = Math.ceil(Math.log(approx) / Math.LN2);
676
    var delta = (log2 <= 48) ? 1 : Math.pow(2, log2 - 48);
677

678
    // Decrease the approximation until it is smaller than the remainder.  Note
679
    // that if it is too large, the product overflows and is negative.
680
    var approxRes = goog.math.Integer.fromNumber(approx);
681
    var approxRem = approxRes.multiply(other);
682
    while (approxRem.isNegative() || approxRem.greaterThan(rem)) {
683
      approx -= delta;
684
      approxRes = goog.math.Integer.fromNumber(approx);
685
      approxRem = approxRes.multiply(other);
686
    }
687

688
    // We know the answer can't be zero... and actually, zero would cause
689
    // infinite recursion since we would make no progress.
690
    if (approxRes.isZero()) {
691
      approxRes = goog.math.Integer.ONE;
692
    }
693

694
    res = res.add(approxRes);
695
    rem = rem.subtract(approxRem);
696
  }
697
  return res;
698
};
699

700

701
/**
702
 * Returns this Integer modulo the given one.
703
 * @param {!goog.math.Integer} other The Integer by which to mod.
704
 * @return {!goog.math.Integer} This value modulo the given one.
705
 */
706
goog.math.Integer.prototype.modulo = function(other) {
707
  return this.subtract(this.divide(other).multiply(other));
708
};
709

710

711
/** @return {!goog.math.Integer} The bitwise-NOT of this value. */
712
goog.math.Integer.prototype.not = function() {
713
  var len = this.bits_.length;
714
  var arr = [];
715
  for (var i = 0; i < len; i++) {
716
    arr[i] = ~this.bits_[i];
717
  }
718
  return new goog.math.Integer(arr, ~this.sign_);
719
};
720

721

722
/**
723
 * Returns the bitwise-AND of this Integer and the given one.
724
 * @param {goog.math.Integer} other The Integer to AND with this.
725
 * @return {!goog.math.Integer} The bitwise-AND of this and the other.
726
 */
727
goog.math.Integer.prototype.and = function(other) {
728
  var len = Math.max(this.bits_.length, other.bits_.length);
729
  var arr = [];
730
  for (var i = 0; i < len; i++) {
731
    arr[i] = this.getBits(i) & other.getBits(i);
732
  }
733
  return new goog.math.Integer(arr, this.sign_ & other.sign_);
734
};
735

736

737
/**
738
 * Returns the bitwise-OR of this Integer and the given one.
739
 * @param {goog.math.Integer} other The Integer to OR with this.
740
 * @return {!goog.math.Integer} The bitwise-OR of this and the other.
741
 */
742
goog.math.Integer.prototype.or = function(other) {
743
  var len = Math.max(this.bits_.length, other.bits_.length);
744
  var arr = [];
745
  for (var i = 0; i < len; i++) {
746
    arr[i] = this.getBits(i) | other.getBits(i);
747
  }
748
  return new goog.math.Integer(arr, this.sign_ | other.sign_);
749
};
750

751

752
/**
753
 * Returns the bitwise-XOR of this Integer and the given one.
754
 * @param {goog.math.Integer} other The Integer to XOR with this.
755
 * @return {!goog.math.Integer} The bitwise-XOR of this and the other.
756
 */
757
goog.math.Integer.prototype.xor = function(other) {
758
  var len = Math.max(this.bits_.length, other.bits_.length);
759
  var arr = [];
760
  for (var i = 0; i < len; i++) {
761
    arr[i] = this.getBits(i) ^ other.getBits(i);
762
  }
763
  return new goog.math.Integer(arr, this.sign_ ^ other.sign_);
764
};
765

766

767
/**
768
 * Returns this value with bits shifted to the left by the given amount.
769
 * @param {number} numBits The number of bits by which to shift.
770
 * @return {!goog.math.Integer} This shifted to the left by the given amount.
771
 */
772
goog.math.Integer.prototype.shiftLeft = function(numBits) {
773
  var arr_delta = numBits >> 5;
774
  var bit_delta = numBits % 32;
775
  var len = this.bits_.length + arr_delta + (bit_delta > 0 ? 1 : 0);
776
  var arr = [];
777
  for (var i = 0; i < len; i++) {
778
    if (bit_delta > 0) {
779
      arr[i] = (this.getBits(i - arr_delta) << bit_delta) |
780
          (this.getBits(i - arr_delta - 1) >>> (32 - bit_delta));
781
    } else {
782
      arr[i] = this.getBits(i - arr_delta);
783
    }
784
  }
785
  return new goog.math.Integer(arr, this.sign_);
786
};
787

788

789
/**
790
 * Returns this value with bits shifted to the right by the given amount.
791
 * @param {number} numBits The number of bits by which to shift.
792
 * @return {!goog.math.Integer} This shifted to the right by the given amount.
793
 */
794
goog.math.Integer.prototype.shiftRight = function(numBits) {
795
  var arr_delta = numBits >> 5;
796
  var bit_delta = numBits % 32;
797
  var len = this.bits_.length - arr_delta;
798
  var arr = [];
799
  for (var i = 0; i < len; i++) {
800
    if (bit_delta > 0) {
801
      arr[i] = (this.getBits(i + arr_delta) >>> bit_delta) |
802
          (this.getBits(i + arr_delta + 1) << (32 - bit_delta));
803
    } else {
804
      arr[i] = this.getBits(i + arr_delta);
805
    }
806
  }
807
  return new goog.math.Integer(arr, this.sign_);
808
};
809

810