< prev index next >

src/java.base/share/classes/java/math/BigInteger.java

 ``` `````` 25 26 /* 27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved. 28 */ 29 30 package java.math; 31 32 import java.io.IOException; 33 import java.io.ObjectInputStream; 34 import java.io.ObjectOutputStream; 35 import java.io.ObjectStreamField; 36 import java.util.Arrays; 37 import java.util.Objects; 38 import java.util.Random; 39 import java.util.concurrent.ThreadLocalRandom; 40 41 import jdk.internal.math.DoubleConsts; 42 import jdk.internal.math.FloatConsts; 43 import jdk.internal.HotSpotIntrinsicCandidate; 44 import jdk.internal.vm.annotation.Stable; 45 46 /** 47 * Immutable arbitrary-precision integers. All operations behave as if 48 * BigIntegers were represented in two's-complement notation (like Java's 49 * primitive integer types). BigInteger provides analogues to all of Java's 50 * primitive integer operators, and all relevant methods from java.lang.Math. 51 * Additionally, BigInteger provides operations for modular arithmetic, GCD 52 * calculation, primality testing, prime generation, bit manipulation, 53 * and a few other miscellaneous operations. 54 * 55 *
Semantics of shift operations extend those of Java's shift operators 61 * to allow for negative shift distances. A right-shift with a negative 62 * shift distance results in a left shift, and vice-versa. The unsigned 63 * right shift operator ({@code >>>}) is omitted since this operation 64 * only makes sense for a fixed sized word and not for a ``````2604 if (n <= (32-bitsInHighWord)) { 2605 primitiveLeftShift(a, len, nBits); 2606 return a; 2607 } else { // Array must be resized 2608 if (nBits <= (32-bitsInHighWord)) { 2609 int result[] = new int[nInts+len]; 2610 System.arraycopy(a, 0, result, 0, len); 2611 primitiveLeftShift(result, result.length, nBits); 2612 return result; 2613 } else { 2614 int result[] = new int[nInts+len+1]; 2615 System.arraycopy(a, 0, result, 0, len); 2616 primitiveRightShift(result, result.length, 32 - nBits); 2617 return result; 2618 } 2619 } 2620 } 2621 2622 // shifts a up to len right n bits assumes no leading zeros, 0 0; i--) { 2626 int b = c; 2627 c = a[i-1]; 2628 a[i] = (c << n2) | (b >>> n); 2629 } 2630 a[0] >>>= n; 2631 } 2632 2633 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32 2634 static void primitiveLeftShift(int[] a, int len, int n) { 2635 if (len == 0 || n == 0) 2636 return; 2637 2638 int n2 = 32 - n; 2639 for (int i=0, c=a[i], m=i+len-1; i < m; i++) { 2640 int b = c; 2641 c = a[i+1]; 2642 a[i] = (b << n) | (c >>> n2); 2643 } 2644 a[len-1] <<= n; 2645 } 2646 2647 /** 2648 * Calculate bitlength of contents of the first len elements an int array, 2649 * assuming there are no leading zero ints. 2650 */ 2651 private static int bitLength(int[] val, int len) { 2652 if (len == 0) 2653 return 0; 2654 return ((len - 1) << 5) + bitLengthForInt(val[0]); 2655 } 2656 2657 /** 2658 * Returns a BigInteger whose value is the absolute value of this 2659 * BigInteger. 2660 * 2661 * @return {@code abs(this)} 2662 */ 2663 public BigInteger abs() { ``````3336 */ 3337 private static int[] shiftLeft(int[] mag, int n) { 3338 int nInts = n >>> 5; 3339 int nBits = n & 0x1f; 3340 int magLen = mag.length; 3341 int newMag[] = null; 3342 3343 if (nBits == 0) { 3344 newMag = new int[magLen + nInts]; 3345 System.arraycopy(mag, 0, newMag, 0, magLen); 3346 } else { 3347 int i = 0; 3348 int nBits2 = 32 - nBits; 3349 int highBits = mag[0] >>> nBits2; 3350 if (highBits != 0) { 3351 newMag = new int[magLen + nInts + 1]; 3352 newMag[i++] = highBits; 3353 } else { 3354 newMag = new int[magLen + nInts]; 3355 } 3356 int j=0; 3357 while (j < magLen-1) 3358 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2; 3359 newMag[i] = mag[j] << nBits; 3360 } 3361 return newMag; 3362 } 3363 3364 /** 3365 * Returns a BigInteger whose value is {@code (this >> n)}. Sign 3366 * extension is performed. The shift distance, {@code n}, may be 3367 * negative, in which case this method performs a left shift. 3368 * (Computes floor(this / 2n).) 3369 * 3370 * @param n shift distance, in bits. 3371 * @return {@code this >> n} 3372 * @see #shiftLeft 3373 */ 3374 public BigInteger shiftRight(int n) { 3375 if (signum == 0) 3376 return ZERO; 3377 if (n > 0) { 3378 return shiftRightImpl(n); 3379 } else if (n == 0) { 3380 return this; 3381 } else { 3382 // Possible int overflow in {@code -n} is not a trouble, 3383 // because shiftLeft considers its argument unsigned ``````3398 int nBits = n & 0x1f; 3399 int magLen = mag.length; 3400 int newMag[] = null; 3401 3402 // Special case: entire contents shifted off the end 3403 if (nInts >= magLen) 3404 return (signum >= 0 ? ZERO : negConst[1]); 3405 3406 if (nBits == 0) { 3407 int newMagLen = magLen - nInts; 3408 newMag = Arrays.copyOf(mag, newMagLen); 3409 } else { 3410 int i = 0; 3411 int highBits = mag[0] >>> nBits; 3412 if (highBits != 0) { 3413 newMag = new int[magLen - nInts]; 3414 newMag[i++] = highBits; 3415 } else { 3416 newMag = new int[magLen - nInts -1]; 3417 } 3418 3419 int nBits2 = 32 - nBits; 3420 int j=0; 3421 while (j < magLen - nInts - 1) 3422 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits); 3423 } 3424 3425 if (signum < 0) { 3426 // Find out whether any one-bits were shifted off the end. 3427 boolean onesLost = false; 3428 for (int i=magLen-1, j=magLen-nInts; i >= j && !onesLost; i--) 3429 onesLost = (mag[i] != 0); 3430 if (!onesLost && nBits != 0) 3431 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0); 3432 3433 if (onesLost) 3434 newMag = javaIncrement(newMag); 3435 } 3436 3437 return new BigInteger(newMag, signum); 3438 } 3439 3440 int[] javaIncrement(int[] val) { 3441 int lastSum = 0; 3442 for (int i=val.length-1; i >= 0 && lastSum == 0; i--) 3443 lastSum = (val[i] += 1); 3444 if (lastSum == 0) { 3445 val = new int[val.length+1]; 3446 val[0] = 1; 3447 } 3448 return val; 3449 } 3450 3451 // Bitwise Operations 3452 3453 /** 3454 * Returns a BigInteger whose value is {@code (this & val)}. (This 3455 * method returns a negative BigInteger if and only if this and val are 3456 * both negative.) 3457 * ``` ``` `````` 25 26 /* 27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved. 28 */ 29 30 package java.math; 31 32 import java.io.IOException; 33 import java.io.ObjectInputStream; 34 import java.io.ObjectOutputStream; 35 import java.io.ObjectStreamField; 36 import java.util.Arrays; 37 import java.util.Objects; 38 import java.util.Random; 39 import java.util.concurrent.ThreadLocalRandom; 40 41 import jdk.internal.math.DoubleConsts; 42 import jdk.internal.math.FloatConsts; 43 import jdk.internal.HotSpotIntrinsicCandidate; 44 import jdk.internal.vm.annotation.Stable; 45 import jdk.internal.vm.annotation.ForceInline; 46 47 /** 48 * Immutable arbitrary-precision integers. All operations behave as if 49 * BigIntegers were represented in two's-complement notation (like Java's 50 * primitive integer types). BigInteger provides analogues to all of Java's 51 * primitive integer operators, and all relevant methods from java.lang.Math. 52 * Additionally, BigInteger provides operations for modular arithmetic, GCD 53 * calculation, primality testing, prime generation, bit manipulation, 54 * and a few other miscellaneous operations. 55 * 56 *
Semantics of shift operations extend those of Java's shift operators 62 * to allow for negative shift distances. A right-shift with a negative 63 * shift distance results in a left shift, and vice-versa. The unsigned 64 * right shift operator ({@code >>>}) is omitted since this operation 65 * only makes sense for a fixed sized word and not for a ``````2605 if (n <= (32-bitsInHighWord)) { 2606 primitiveLeftShift(a, len, nBits); 2607 return a; 2608 } else { // Array must be resized 2609 if (nBits <= (32-bitsInHighWord)) { 2610 int result[] = new int[nInts+len]; 2611 System.arraycopy(a, 0, result, 0, len); 2612 primitiveLeftShift(result, result.length, nBits); 2613 return result; 2614 } else { 2615 int result[] = new int[nInts+len+1]; 2616 System.arraycopy(a, 0, result, 0, len); 2617 primitiveRightShift(result, result.length, 32 - nBits); 2618 return result; 2619 } 2620 } 2621 } 2622 2623 // shifts a up to len right n bits assumes no leading zeros, 0>>= n; 2628 } 2629 2630 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32 2631 static void primitiveLeftShift(int[] a, int len, int n) { 2632 if (len == 0 || n == 0) 2633 return; 2634 Objects.checkFromToIndex(0, len, a.length); 2635 shiftLeftImplWorker(a, a, 0, n, len-1); 2636 a[len-1] <<= n; 2637 } 2638 2639 /** 2640 * Calculate bitlength of contents of the first len elements an int array, 2641 * assuming there are no leading zero ints. 2642 */ 2643 private static int bitLength(int[] val, int len) { 2644 if (len == 0) 2645 return 0; 2646 return ((len - 1) << 5) + bitLengthForInt(val[0]); 2647 } 2648 2649 /** 2650 * Returns a BigInteger whose value is the absolute value of this 2651 * BigInteger. 2652 * 2653 * @return {@code abs(this)} 2654 */ 2655 public BigInteger abs() { ``````3328 */ 3329 private static int[] shiftLeft(int[] mag, int n) { 3330 int nInts = n >>> 5; 3331 int nBits = n & 0x1f; 3332 int magLen = mag.length; 3333 int newMag[] = null; 3334 3335 if (nBits == 0) { 3336 newMag = new int[magLen + nInts]; 3337 System.arraycopy(mag, 0, newMag, 0, magLen); 3338 } else { 3339 int i = 0; 3340 int nBits2 = 32 - nBits; 3341 int highBits = mag[0] >>> nBits2; 3342 if (highBits != 0) { 3343 newMag = new int[magLen + nInts + 1]; 3344 newMag[i++] = highBits; 3345 } else { 3346 newMag = new int[magLen + nInts]; 3347 } 3348 int numIter = magLen - 1; 3349 Objects.checkFromToIndex(0, numIter + 1, mag.length); 3350 Objects.checkFromToIndex(i, numIter + i + 1, newMag.length); 3351 shiftLeftImplWorker(newMag, mag, i, nBits, numIter); 3352 newMag[numIter + i] = mag[numIter] << nBits; 3353 } 3354 return newMag; 3355 } 3356 3357 @ForceInline 3358 @HotSpotIntrinsicCandidate 3359 private static void shiftLeftImplWorker(int[] newArr, int[] oldArr, int newIdx, int shiftCount, int numIter) { 3360 int shiftCountRight = 32 - shiftCount; 3361 int oldIdx = 0; 3362 while (oldIdx < numIter) { 3363 newArr[newIdx++] = (oldArr[oldIdx++] << shiftCount) | (oldArr[oldIdx] >>> shiftCountRight); 3364 } 3365 } 3366 3367 /** 3368 * Returns a BigInteger whose value is {@code (this >> n)}. Sign 3369 * extension is performed. The shift distance, {@code n}, may be 3370 * negative, in which case this method performs a left shift. 3371 * (Computes floor(this / 2n).) 3372 * 3373 * @param n shift distance, in bits. 3374 * @return {@code this >> n} 3375 * @see #shiftLeft 3376 */ 3377 public BigInteger shiftRight(int n) { 3378 if (signum == 0) 3379 return ZERO; 3380 if (n > 0) { 3381 return shiftRightImpl(n); 3382 } else if (n == 0) { 3383 return this; 3384 } else { 3385 // Possible int overflow in {@code -n} is not a trouble, 3386 // because shiftLeft considers its argument unsigned ``````3401 int nBits = n & 0x1f; 3402 int magLen = mag.length; 3403 int newMag[] = null; 3404 3405 // Special case: entire contents shifted off the end 3406 if (nInts >= magLen) 3407 return (signum >= 0 ? ZERO : negConst[1]); 3408 3409 if (nBits == 0) { 3410 int newMagLen = magLen - nInts; 3411 newMag = Arrays.copyOf(mag, newMagLen); 3412 } else { 3413 int i = 0; 3414 int highBits = mag[0] >>> nBits; 3415 if (highBits != 0) { 3416 newMag = new int[magLen - nInts]; 3417 newMag[i++] = highBits; 3418 } else { 3419 newMag = new int[magLen - nInts -1]; 3420 } 3421 int numIter = magLen - nInts - 1; 3422 Objects.checkFromToIndex(0, numIter + 1, mag.length); 3423 Objects.checkFromToIndex(i, numIter + i, newMag.length); 3424 shiftRightImplWorker(newMag, mag, i, nBits, numIter); 3425 } 3426 3427 if (signum < 0) { 3428 // Find out whether any one-bits were shifted off the end. 3429 boolean onesLost = false; 3430 for (int i=magLen-1, j=magLen-nInts; i >= j && !onesLost; i--) 3431 onesLost = (mag[i] != 0); 3432 if (!onesLost && nBits != 0) 3433 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0); 3434 3435 if (onesLost) 3436 newMag = javaIncrement(newMag); 3437 } 3438 3439 return new BigInteger(newMag, signum); 3440 } 3441 3442 @ForceInline 3443 @HotSpotIntrinsicCandidate 3444 private static void shiftRightImplWorker(int[] newArr, int[] oldArr, int newIdx, int shiftCount, int numIter) { 3445 int shiftCountLeft = 32 - shiftCount; 3446 int idx = numIter; 3447 int nidx = (newIdx == 0) ? numIter - 1 : numIter; 3448 while (nidx >= newIdx) { 3449 newArr[nidx--] = (oldArr[idx--] >>> shiftCount) | (oldArr[idx] << shiftCountLeft); 3450 } 3451 } 3452 3453 int[] javaIncrement(int[] val) { 3454 int lastSum = 0; 3455 for (int i=val.length-1; i >= 0 && lastSum == 0; i--) 3456 lastSum = (val[i] += 1); 3457 if (lastSum == 0) { 3458 val = new int[val.length+1]; 3459 val[0] = 1; 3460 } 3461 return val; 3462 } 3463 3464 // Bitwise Operations 3465 3466 /** 3467 * Returns a BigInteger whose value is {@code (this & val)}. (This 3468 * method returns a negative BigInteger if and only if this and val are 3469 * both negative.) 3470 * ```