< prev index next >

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

Print this page




  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  * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
  56  * arithmetic operators, as defined in <i>The Java&trade; Language Specification</i>.
  57  * For example, division by zero throws an {@code ArithmeticException}, and
  58  * division of a negative by a positive yields a negative (or zero) remainder.
  59  *
  60  * <p>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<n<32
2623     static void primitiveRightShift(int[] a, int len, int n) {
2624         int n2 = 32 - n;
2625         for (int i=len-1, c=a[i]; i > 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 <code>floor(this / 2<sup>n</sup>)</code>.)
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  * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
  57  * arithmetic operators, as defined in <i>The Java&trade; Language Specification</i>.
  58  * For example, division by zero throws an {@code ArithmeticException}, and
  59  * division of a negative by a positive yields a negative (or zero) remainder.
  60  *
  61  * <p>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<32
2624     static void primitiveRightShift(int[] a, int len, int n) {
2625         Objects.checkFromToIndex(0, len, a.length);
2626         shiftRightImplWorker(a, a, 1, n, len-1);




2627         a[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 <code>floor(this / 2<sup>n</sup>)</code>.)
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      *


< prev index next >