/* * Copyright 2005 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. *//* * @(#)BigInteger.java	1.70 05/08/09 */package java.math;import java.util.Random;import java.io.*;/** * Immutable arbitrary-precision integers.  All operations behave as if * BigIntegers were represented in two's-complement notation (like Java's * primitive integer types).  BigInteger provides analogues to all of Java's * primitive integer operators, and all relevant methods from java.lang.Math. * Additionally, BigInteger provides operations for modular arithmetic, GCD * calculation, primality testing, prime generation, bit manipulation, * and a few other miscellaneous operations. * <p> * Semantics of arithmetic operations exactly mimic those of Java's integer * arithmetic operators, as defined in <i>The Java Language Specification</i>. * For example, division by zero throws an <tt>ArithmeticException</tt>, and * division of a negative by a positive yields a negative (or zero) remainder. * All of the details in the Spec concerning overflow are ignored, as * BigIntegers are made as large as necessary to accommodate the results of an * operation. * <p> * Semantics of shift operations extend those of Java's shift operators * to allow for negative shift distances.  A right-shift with a negative * shift distance results in a left shift, and vice-versa.  The unsigned * right shift operator (&gt;&gt;&gt;) is omitted, as this operation makes * little sense in combination with the "infinite word size" abstraction * provided by this class. * <p> * Semantics of bitwise logical operations exactly mimic those of Java's * bitwise integer operators.  The binary operators (<tt>and</tt>, * <tt>or</tt>, <tt>xor</tt>) implicitly perform sign extension on the shorter * of the two operands prior to performing the operation. * <p> * Comparison operations perform signed integer comparisons, analogous to * those performed by Java's relational and equality operators. * <p> * Modular arithmetic operations are provided to compute residues, perform * exponentiation, and compute multiplicative inverses.  These methods always * return a non-negative result, between <tt>0</tt> and <tt>(modulus - 1)</tt>, * inclusive. * <p> * Bit operations operate on a single bit of the two's-complement * representation of their operand.  If necessary, the operand is sign- * extended so that it contains the designated bit.  None of the single-bit * operations can produce a BigInteger with a different sign from the * BigInteger being operated on, as they affect only a single bit, and the * "infinite word size" abstraction provided by this class ensures that there * are infinitely many "virtual sign bits" preceding each BigInteger. * <p> * For the sake of brevity and clarity, pseudo-code is used throughout the * descriptions of BigInteger methods.  The pseudo-code expression * <tt>(i + j)</tt> is shorthand for "a BigInteger whose value is * that of the BigInteger <tt>i</tt> plus that of the BigInteger <tt>j</tt>." * The pseudo-code expression <tt>(i == j)</tt> is shorthand for * "<tt>true</tt> if and only if the BigInteger <tt>i</tt> represents the same * value as the BigInteger <tt>j</tt>."  Other pseudo-code expressions are * interpreted similarly. * <p> * All methods and constructors in this class throw * <CODE>NullPointerException</CODE> when passed * a null object reference for any input parameter. * * @see     BigDecimal * @version 1.70, 08/09/05 * @author  Josh Bloch * @author  Michael McCloskey * @since JDK1.1 */public class BigInteger extends Number implements Comparable<BigInteger> {    /**     * The signum of this BigInteger: -1 for negative, 0 for zero, or     * 1 for positive.  Note that the BigInteger zero <i>must</i> have     * a signum of 0.  This is necessary to ensures that there is exactly one     * representation for each BigInteger value.     *     * @serial     */    int signum;    /**     * The magnitude of this BigInteger, in <i>big-endian</i> order: the     * zeroth element of this array is the most-significant int of the     * magnitude.  The magnitude must be "minimal" in that the most-significant     * int (<tt>mag[0]</tt>) must be non-zero.  This is necessary to     * ensure that there is exactly one representation for each BigInteger     * value.  Note that this implies that the BigInteger zero has a     * zero-length mag array.     */    int[] mag;    // These "redundant fields" are initialized with recognizable nonsense    // values, and cached the first time they are needed (or never, if they    // aren't needed).    /**     * The bitCount of this BigInteger, as returned by bitCount(), or -1     * (either value is acceptable).     *     * @serial     * @see #bitCount     */    private int bitCount =  -1;    /**     * The bitLength of this BigInteger, as returned by bitLength(), or -1     * (either value is acceptable).     *     * @serial     * @see #bitLength     */    private int bitLength = -1;    /**     * The lowest set bit of this BigInteger, as returned by getLowestSetBit(),     * or -2 (either value is acceptable).     *     * @serial     * @see #getLowestSetBit     */    private int lowestSetBit = -2;    /**     * The index of the lowest-order byte in the magnitude of this BigInteger     * that contains a nonzero byte, or -2 (either value is acceptable).  The     * least significant byte has int-number 0, the next byte in order of     * increasing significance has byte-number 1, and so forth.     *     * @serial     */    private int firstNonzeroByteNum = -2;    /**     * The index of the lowest-order int in the magnitude of this BigInteger     * that contains a nonzero int, or -2 (either value is acceptable).  The     * least significant int has int-number 0, the next int in order of     * increasing significance has int-number 1, and so forth.     */    private int firstNonzeroIntNum = -2;    /**     * This mask is used to obtain the value of an int as if it were unsigned.     */    private final static long LONG_MASK = 0xffffffffL;    //Constructors    /**     * Translates a byte array containing the two's-complement binary     * representation of a BigInteger into a BigInteger.  The input array is     * assumed to be in <i>big-endian</i> byte-order: the most significant     * byte is in the zeroth element.     *     * @param  val big-endian two's-complement binary representation of     *	       BigInteger.     * @throws NumberFormatException <tt>val</tt> is zero bytes long.     */    public BigInteger(byte[] val) {	if (val.length == 0)	    throw new NumberFormatException("Zero length BigInteger");	if (val[0] < 0) {            mag = makePositive(val);	    signum = -1;	} else {	    mag = stripLeadingZeroBytes(val);	    signum = (mag.length == 0 ? 0 : 1);	}    }    /**     * This private constructor translates an int array containing the     * two's-complement binary representation of a BigInteger into a     * BigInteger. The input array is assumed to be in <i>big-endian</i>     * int-order: the most significant int is in the zeroth element.     */    private BigInteger(int[] val) {	if (val.length == 0)	    throw new NumberFormatException("Zero length BigInteger");	if (val[0] < 0) {            mag = makePositive(val);	    signum = -1;	} else {	    mag = trustedStripLeadingZeroInts(val);	    signum = (mag.length == 0 ? 0 : 1);	}    }    /**     * Translates the sign-magnitude representation of a BigInteger into a     * BigInteger.  The sign is represented as an integer signum value: -1 for     * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array     * in <i>big-endian</i> byte-order: the most significant byte is in the     * zeroth element.  A zero-length magnitude array is permissible, and will     * result inin a BigInteger value of 0, whether signum is -1, 0 or 1.     *     * @param  signum signum of the number (-1 for negative, 0 for zero, 1     * 	       for positive).     * @param  magnitude big-endian binary representation of the magnitude of     * 	       the number.     * @throws NumberFormatException <tt>signum</tt> is not one of the three     *	       legal values (-1, 0, and 1), or <tt>signum</tt> is 0 and     *	       <tt>magnitude</tt> contains one or more non-zero bytes.     */    public BigInteger(int signum, byte[] magnitude) {	this.mag = stripLeadingZeroBytes(magnitude);	if (signum < -1 || signum > 1)	    throw(new NumberFormatException("Invalid signum value"));	if (this.mag.length==0) {	    this.signum = 0;	} else {	    if (signum == 0)		throw(new NumberFormatException("signum-magnitude mismatch"));	    this.signum = signum;	}    }    /**     * A constructor for internal use that translates the sign-magnitude     * representation of a BigInteger into a BigInteger. It checks the     * arguments and copies the magnitude so this constructor would be     * safe for external use.     */    private BigInteger(int signum, int[] magnitude) {	this.mag = stripLeadingZeroInts(magnitude);	if (signum < -1 || signum > 1)	    throw(new NumberFormatException("Invalid signum value"));	if (this.mag.length==0) {	    this.signum = 0;	} else {	    if (signum == 0)		throw(new NumberFormatException("signum-magnitude mismatch"));	    this.signum = signum;	}    }    /**     * Translates the String representation of a BigInteger in the specified     * radix into a BigInteger.  The String representation consists of an     * optional minus sign followed by a sequence of one or more digits in the     * specified radix.  The character-to-digit mapping is provided by     * <tt>Character.digit</tt>.  The String may not contain any extraneous     * characters (whitespace, for example).     *     * @param val String representation of BigInteger.     * @param radix radix to be used in interpreting <tt>val</tt>.     * @throws NumberFormatException <tt>val</tt> is not a valid representation     *	       of a BigInteger in the specified radix, or <tt>radix</tt> is     *	       outside the range from {@link Character#MIN_RADIX} to     *	       {@link Character#MAX_RADIX}, inclusive.     * @see    Character#digit     */    public BigInteger(String val, int radix) {	int cursor = 0, numDigits;        int len = val.length();	if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)	    throw new NumberFormatException("Radix out of range");	if (val.length() == 0)	    throw new NumberFormatException("Zero length BigInteger");	// Check for minus sign	signum = 1;        int index = val.lastIndexOf("-");        if (index != -1) {            if (index == 0) {                if (val.length() == 1)                    throw new NumberFormatException("Zero length BigInteger");                signum = -1;                cursor = 1;            } else {                throw new NumberFormatException("Illegal embedded minus sign");            }        }        // Skip leading zeros and compute number of digits in magnitude	while (cursor < len &&               Character.digit(val.charAt(cursor),radix) == 0)	    cursor++;	if (cursor == len) {	    signum = 0;	    mag = ZERO.mag;	    return;	} else {	    numDigits = len - cursor;	}        // Pre-allocate array of expected size. May be too large but can        // never be too small. Typically exact.        int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1);        int numWords = (numBits + 31) /32;        mag = new int[numWords];	// Process first (potentially short) digit group	int firstGroupLen = numDigits % digitsPerInt[radix];	if (firstGroupLen == 0)	    firstGroupLen = digitsPerInt[radix];	String group = val.substring(cursor, cursor += firstGroupLen);        mag[mag.length - 1] = Integer.parseInt(group, radix);	if (mag[mag.length - 1] < 0)	    throw new NumberFormatException("Illegal digit");        	// Process remaining digit groups        int superRadix = intRadix[radix];        int groupVal = 0;	while (cursor < val.length()) {	    group = val.substring(cursor, cursor += digitsPerInt[radix]);	    groupVal = Integer.parseInt(group, radix);	    if (groupVal < 0)		throw new NumberFormatException("Illegal digit");            destructiveMulAdd(mag, superRadix, groupVal);	}        // Required for cases where the array was overallocated.        mag = trustedStripLeadingZeroInts(mag);    }    // Constructs a new BigInteger using a char array with radix=10    BigInteger(char[] val) {        int cursor = 0, numDigits;        int len = val.length;	// Check for leading minus sign	signum = 1;	if (val[0] == '-') {	    if (len == 1)		throw new NumberFormatException("Zero length BigInteger");	    signum = -1;	    cursor = 1;	}        // Skip leading zeros and compute number of digits in magnitude	while (cursor < len && Character.digit(val[cursor], 10) == 0)	    cursor++;	if (cursor == len) {	    signum = 0;	    mag = ZERO.mag;	    return;	} else {	    numDigits = len - cursor;	}        // Pre-allocate array of expected size        int numWords;        if (len < 10) {            numWords = 1;        } else {                int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);            numWords = (numBits + 31) /32;        }        mag = new int[numWords]; 	// Process first (potentially short) digit group	int firstGroupLen = numDigits % digitsPerInt[10];	if (firstGroupLen == 0)	    firstGroupLen = digitsPerInt[10];        mag[mag.length-1] = parseInt(val, cursor,  cursor += firstGroupLen);        	// Process remaining digit groups	while (cursor < len) {	    int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);            destructiveMulAdd(mag, intRadix[10], groupVal);	}        mag = trustedStripLeadingZeroInts(mag);