Debian Codegraph @

closure-library/closure/goog/math/integer.js

raw
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 new Error('number format error: empty string');
157 }
158
159 var radix = opt_radix || 10;
160 if (radix < 2 || 36 < radix) {
161 throw new 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 new 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 new 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 new 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 new 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 };