src/share/classes/java/math/BigInteger.java
Print this page
@@ -103,11 +103,11 @@
* a signum of 0. This is necessary to ensures that there is exactly one
* representation for each BigInteger value.
*
* @serial
*/
- int signum;
+ final 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
@@ -114,65 +114,66 @@
* int ({@code mag[0]}) 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;
+ final 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).
+ * One plus the bitCount of this BigInteger. Zeros means unitialized.
*
* @serial
* @see #bitCount
+ * @deprecated Deprecated since logical value is offset from stored
+ * value and correction factor is applied in accessor method.
*/
- private int bitCount = -1;
+ @Deprecated
+ private int bitCount;
/**
- * The bitLength of this BigInteger, as returned by bitLength(), or -1
+ * One plus the bitLength of this BigInteger. Zeros means unitialized.
* (either value is acceptable).
*
* @serial
* @see #bitLength()
+ * @deprecated Deprecated since logical value is offset from stored
+ * value and correction factor is applied in accessor method.
*/
- private int bitLength = -1;
+ @Deprecated
+ private int bitLength;
/**
- * The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
- * or -2 (either value is acceptable).
+ * Two plus the lowest set bit of this BigInteger, as returned by
+ * getLowestSetBit().
*
* @serial
* @see #getLowestSetBit
+ * @deprecated Deprecated since logical value is offset from stored
+ * value and correction factor is applied in accessor method.
*/
- private int lowestSetBit = -2;
+ @Deprecated
+ private int lowestSetBit;
/**
- * 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
+ * Two plus 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.
+ * @deprecated Deprecated since logical value is offset from stored
+ * value and correction factor is applied in accessor method.
*/
- private int firstNonzeroIntNum = -2;
+ @Deprecated
+ private int firstNonzeroIntNum;
/**
* This mask is used to obtain the value of an int as if it were unsigned.
*/
- private final static long LONG_MASK = 0xffffffffL;
+ final static long LONG_MASK = 0xffffffffL;
//Constructors
/**
* Translates a byte array containing the two's-complement binary
@@ -293,11 +294,11 @@
throw new NumberFormatException("Radix out of range");
if (val.length() == 0)
throw new NumberFormatException("Zero length BigInteger");
// Check for at most one leading sign
- signum = 1;
+ int sign = 1;
int index1 = val.lastIndexOf('-');
int index2 = val.lastIndexOf('+');
if ((index1 + index2) <= -1) {
// No leading sign character or at most one leading sign character
if (index1 == 0 || index2 == 0) {
@@ -304,11 +305,11 @@
cursor = 1;
if (val.length() == 1)
throw new NumberFormatException("Zero length BigInteger");
}
if (index1 == 0)
- signum = -1;
+ sign = -1;
} else
throw new NumberFormatException("Illegal embedded sign character");
// Skip leading zeros and compute number of digits in magnitude
while (cursor < len &&
@@ -316,27 +317,28 @@
cursor++;
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
- } else {
- numDigits = len - cursor;
}
+ numDigits = len - cursor;
+ signum = sign;
+
// 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];
+ int numWords = (numBits + 31) >>> 5;
+ int[] magnitude = 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)
+ magnitude[numWords - 1] = Integer.parseInt(group, radix);
+ if (magnitude[numWords - 1] < 0)
throw new NumberFormatException("Illegal digit");
// Process remaining digit groups
int superRadix = intRadix[radix];
int groupVal = 0;
@@ -343,27 +345,27 @@
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);
+ destructiveMulAdd(magnitude, superRadix, groupVal);
}
// Required for cases where the array was overallocated.
- mag = trustedStripLeadingZeroInts(mag);
+ mag = trustedStripLeadingZeroInts(magnitude);
}
// 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;
+ int sign = 1;
if (val[0] == '-') {
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
- signum = -1;
+ sign = -1;
cursor = 1;
} else if (val[0] == '+') {
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
cursor = 1;
@@ -374,36 +376,37 @@
cursor++;
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
- } else {
- numDigits = len - cursor;
}
+ numDigits = len - cursor;
+ signum = sign;
+
// 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;
+ numWords = (numBits + 31) >>> 5;
}
- mag = new int[numWords];
+ int[] magnitude = 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);
+ magnitude[numWords - 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);
+ destructiveMulAdd(magnitude, intRadix[10], groupVal);
}
- mag = trustedStripLeadingZeroInts(mag);
+ mag = trustedStripLeadingZeroInts(magnitude);
}
// Create an integer with the digits between the two indexes
// Assumes start < end. The result may be negative, but it
// is to be treated as an unsigned value.
@@ -840,30 +843,25 @@
for (int i=k.bitLength()-2; i>=0; i--) {
u2 = u.multiply(v).mod(n);
v2 = v.square().add(d.multiply(u.square())).mod(n);
- if (v2.testBit(0)) {
- v2 = n.subtract(v2);
- v2.signum = - v2.signum;
- }
+ if (v2.testBit(0))
+ v2 = v2.subtract(n);
+
v2 = v2.shiftRight(1);
u = u2; v = v2;
if (k.testBit(i)) {
u2 = u.add(v).mod(n);
- if (u2.testBit(0)) {
- u2 = n.subtract(u2);
- u2.signum = - u2.signum;
- }
- u2 = u2.shiftRight(1);
+ if (u2.testBit(0))
+ u2 = u2.subtract(n);
+ u2 = u2.shiftRight(1);
v2 = v.add(d.multiply(u)).mod(n);
- if (v2.testBit(0)) {
- v2 = n.subtract(v2);
- v2.signum = - v2.signum;
- }
+ if (v2.testBit(0))
+ v2 = v2.subtract(n);
v2 = v2.shiftRight(1);
u = u2; v = v2;
}
}
@@ -916,15 +914,15 @@
}
return true;
}
/**
- * This private constructor differs from its public cousin
+ * This internal constructor differs from its public cousin
* with the arguments reversed in two ways: it assumes that its
* arguments are correct, and it doesn't copy the magnitude array.
*/
- private BigInteger(int[] magnitude, int signum) {
+ BigInteger(int[] magnitude, int signum) {
this.signum = (magnitude.length==0 ? 0 : signum);
this.mag = magnitude;
}
/**
@@ -934,26 +932,10 @@
private BigInteger(byte[] magnitude, int signum) {
this.signum = (magnitude.length==0 ? 0 : signum);
this.mag = stripLeadingZeroBytes(magnitude);
}
- /**
- * This private constructor is for internal use in converting
- * from a MutableBigInteger object into a BigInteger.
- */
- BigInteger(MutableBigInteger val, int sign) {
- if (val.offset > 0 || val.value.length != val.intLen) {
- mag = new int[val.intLen];
- for(int i=0; i<val.intLen; i++)
- mag[i] = val.value[val.offset+i];
- } else {
- mag = val.value;
- }
-
- this.signum = (val.intLen == 0) ? 0 : sign;
- }
-
//Static Factory Methods
/**
* Returns a BigInteger whose value is equal to that of the
* specified {@code long}. This "static factory method" is
@@ -978,12 +960,12 @@
/**
* Constructs a BigInteger with the specified value, which may not be zero.
*/
private BigInteger(long val) {
if (val < 0) {
- signum = -1;
val = -val;
+ signum = -1;
} else {
signum = 1;
}
int highWord = (int)(val >>> 32);
@@ -1056,26 +1038,25 @@
*
* @param val value to be added to this BigInteger.
* @return {@code this + val}
*/
public BigInteger add(BigInteger val) {
- int[] resultMag;
if (val.signum == 0)
return this;
if (signum == 0)
return val;
if (val.signum == signum)
return new BigInteger(add(mag, val.mag), signum);
- int cmp = intArrayCmp(mag, val.mag);
- if (cmp==0)
+ int cmp = compareMagnitude(val);
+ if (cmp == 0)
return ZERO;
- resultMag = (cmp>0 ? subtract(mag, val.mag)
+ int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
: subtract(val.mag, mag));
resultMag = trustedStripLeadingZeroInts(resultMag);
- return new BigInteger(resultMag, cmp*signum);
+ return new BigInteger(resultMag, cmp == signum ? 1 : -1);
}
/**
* Adds the contents of the int arrays x and y. This method allocates
* a new int array to hold the answer and returns a reference to that
@@ -1110,16 +1091,14 @@
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
- int newLen = result.length + 1;
- int temp[] = new int[newLen];
- for (int i = 1; i<newLen; i++)
- temp[i] = result[i-1];
- temp[0] = 0x01;
- result = temp;
+ int bigger[] = new int[result.length + 1];
+ System.arraycopy(result, 0, bigger, 1, result.length);
+ bigger[0] = 0x01;
+ return bigger;
}
return result;
}
/**
@@ -1127,25 +1106,24 @@
*
* @param val value to be subtracted from this BigInteger.
* @return {@code this - val}
*/
public BigInteger subtract(BigInteger val) {
- int[] resultMag;
if (val.signum == 0)
return this;
if (signum == 0)
return val.negate();
if (val.signum != signum)
return new BigInteger(add(mag, val.mag), signum);
- int cmp = intArrayCmp(mag, val.mag);
- if (cmp==0)
+ int cmp = compareMagnitude(val);
+ if (cmp == 0)
return ZERO;
- resultMag = (cmp>0 ? subtract(mag, val.mag)
+ int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
: subtract(val.mag, mag));
resultMag = trustedStripLeadingZeroInts(resultMag);
- return new BigInteger(resultMag, cmp*signum);
+ return new BigInteger(resultMag, cmp == signum ? 1 : -1);
}
/**
* Subtracts the contents of the second int arrays (little) from the
* first (big). The first int array (big) must represent a larger number
@@ -1189,16 +1167,57 @@
return ZERO;
int[] result = multiplyToLen(mag, mag.length,
val.mag, val.mag.length, null);
result = trustedStripLeadingZeroInts(result);
- return new BigInteger(result, signum*val.signum);
+ return new BigInteger(result, signum == val.signum ? 1 : -1);
}
/**
+ * Package private methods used by BigDecimal code to multiply a BigInteger
+ * with a long. Assumes v is not equal to INFLATED.
+ */
+ BigInteger multiply(long v) {
+ if (v == 0 || signum == 0)
+ return ZERO;
+ assert v != BigDecimal.INFLATED;
+ int rsign = (v > 0 ? signum : -signum);
+ if (v < 0)
+ v = -v;
+ long dh = v >>> 32; // higher order bits
+ long dl = v & LONG_MASK; // lower order bits
+
+ int xlen = mag.length;
+ int[] value = mag;
+ int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
+ long carry = 0;
+ int rstart = rmag.length - 1;
+ for (int i = xlen - 1; i >= 0; i--) {
+ long product = (value[i] & LONG_MASK) * dl + carry;
+ rmag[rstart--] = (int)product;
+ carry = product >>> 32;
+ }
+ rmag[rstart] = (int)carry;
+ if (dh != 0L) {
+ carry = 0;
+ rstart = rmag.length - 2;
+ for (int i = xlen - 1; i >= 0; i--) {
+ long product = (value[i] & LONG_MASK) * dh +
+ (rmag[rstart] & LONG_MASK) + carry;
+ rmag[rstart--] = (int)product;
+ carry = product >>> 32;
+ }
+ rmag[0] = (int)carry;
+ }
+ if (carry == 0L)
+ rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
+ return new BigInteger(rmag, rsign);
+ }
+
+ /**
* Multiplies int arrays x and y to the specified lengths and places
- * the result into z.
+ * the result into z. There will be no leading zeros in the resultant array.
*/
private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
int xstart = xlen - 1;
int ystart = ylen - 1;
@@ -1314,16 +1333,15 @@
* @return {@code this / val}
* @throws ArithmeticException {@code val==0}
*/
public BigInteger divide(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
- r = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
- a.divide(b, q, r);
- return new BigInteger(q, this.signum * val.signum);
+ a.divide(b, q);
+ return q.toBigInteger(this.signum == val.signum ? 1 : -1);
}
/**
* Returns an array of two BigIntegers containing {@code (this / val)}
* followed by {@code (this % val)}.
@@ -1336,16 +1354,15 @@
* @throws ArithmeticException {@code val==0}
*/
public BigInteger[] divideAndRemainder(BigInteger val) {
BigInteger[] result = new BigInteger[2];
MutableBigInteger q = new MutableBigInteger(),
- r = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
- a.divide(b, q, r);
- result[0] = new BigInteger(q, this.signum * val.signum);
- result[1] = new BigInteger(r, this.signum);
+ MutableBigInteger r = a.divide(b, q);
+ result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
+ result[1] = r.toBigInteger(this.signum);
return result;
}
/**
* Returns a BigInteger whose value is {@code (this % val)}.
@@ -1355,16 +1372,14 @@
* @return {@code this % val}
* @throws ArithmeticException {@code val==0}
*/
public BigInteger remainder(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
- r = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
- a.divide(b, q, r);
- return new BigInteger(r, this.signum);
+ return a.divide(b, q).toBigInteger(this.signum);
}
/**
* Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
* Note that {@code exponent} is an integer rather than a BigInteger.
@@ -1416,21 +1431,28 @@
MutableBigInteger a = new MutableBigInteger(this);
MutableBigInteger b = new MutableBigInteger(val);
MutableBigInteger result = a.hybridGCD(b);
- return new BigInteger(result, 1);
+ return result.toBigInteger(1);
}
/**
+ * Package private method to return bit length for an integer.
+ */
+ static int bitLengthForInt(int n) {
+ return 32 - Integer.numberOfLeadingZeros(n);
+ }
+
+ /**
* Left shift int array a up to len by n bits. Returns the array that
* results from the shift since space may have to be reallocated.
*/
private static int[] leftShift(int[] a, int len, int n) {
int nInts = n >>> 5;
int nBits = n&0x1F;
- int bitsInHighWord = bitLen(a[0]);
+ int bitsInHighWord = bitLengthForInt(a[0]);
// If shift can be done without recopy, do so
if (n <= (32-bitsInHighWord)) {
primitiveLeftShift(a, len, nBits);
return a;
@@ -1479,13 +1501,13 @@
/**
* Calculate bitlength of contents of the first len elements an int array,
* assuming there are no leading zero ints.
*/
private static int bitLength(int[] val, int len) {
- if (len==0)
+ if (len == 0)
return 0;
- return ((len-1)<<5) + bitLen(val[0]);
+ return ((len - 1) << 5) + bitLengthForInt(val[0]);
}
/**
* Returns a BigInteger whose value is the absolute value of this
* BigInteger.
@@ -1708,15 +1730,14 @@
// Convert base to Montgomery form
int[] a = leftShift(base, base.length, modLen << 5);
MutableBigInteger q = new MutableBigInteger(),
- r = new MutableBigInteger(),
a2 = new MutableBigInteger(a),
b2 = new MutableBigInteger(mod);
- a2.divide(b2, q, r);
+ MutableBigInteger r= a2.divide(b2, q);
table[0] = r.toIntArray();
// Pad table[0] with leading zeros so its length is at least modLen
if (table[0].length < modLen) {
int offset = modLen - table[0].length;
@@ -1974,11 +1995,11 @@
private BigInteger mod2(int p) {
if (bitLength() <= p)
return this;
// Copy remaining ints of mag
- int numInts = (p+31)/32;
+ int numInts = (p + 31) >>> 5;
int[] mag = new int[numInts];
for (int i=0; i<numInts; i++)
mag[i] = this.mag[i + (this.mag.length - numInts)];
// Mask out any excess bits
@@ -2004,21 +2025,21 @@
if (m.equals(ONE))
return ZERO;
// Calculate (this mod m)
BigInteger modVal = this;
- if (signum < 0 || (intArrayCmp(mag, m.mag) >= 0))
+ if (signum < 0 || (this.compareMagnitude(m) >= 0))
modVal = this.mod(m);
if (modVal.equals(ONE))
return ONE;
MutableBigInteger a = new MutableBigInteger(modVal);
MutableBigInteger b = new MutableBigInteger(m);
MutableBigInteger result = a.mutableModInverse(b);
- return new BigInteger(result, 1);
+ return result.toBigInteger(1);
}
// Shift Operations
/**
@@ -2239,11 +2260,11 @@
*/
public boolean testBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
- return (getInt(n/32) & (1 << (n%32))) != 0;
+ return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
}
/**
* Returns a BigInteger whose value is equivalent to this BigInteger
* with the designated bit set. (Computes {@code (this | (1<<n))}.)
@@ -2254,17 +2275,17 @@
*/
public BigInteger setBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
- int intNum = n/32;
+ int intNum = n >>> 5;
int[] result = new int[Math.max(intLength(), intNum+2)];
for (int i=0; i<result.length; i++)
result[result.length-i-1] = getInt(i);
- result[result.length-intNum-1] |= (1 << (n%32));
+ result[result.length-intNum-1] |= (1 << (n & 31));
return valueOf(result);
}
/**
@@ -2278,17 +2299,17 @@
*/
public BigInteger clearBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
- int intNum = n/32;
- int[] result = new int[Math.max(intLength(), (n+1)/32+1)];
+ int intNum = n >>> 5;
+ int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)];
for (int i=0; i<result.length; i++)
result[result.length-i-1] = getInt(i);
- result[result.length-intNum-1] &= ~(1 << (n%32));
+ result[result.length-intNum-1] &= ~(1 << (n & 31));
return valueOf(result);
}
/**
@@ -2302,17 +2323,17 @@
*/
public BigInteger flipBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
- int intNum = n/32;
+ int intNum = n >>> 5;
int[] result = new int[Math.max(intLength(), intNum+2)];
for (int i=0; i<result.length; i++)
result[result.length-i-1] = getInt(i);
- result[result.length-intNum-1] ^= (1 << (n%32));
+ result[result.length-intNum-1] ^= (1 << (n & 31));
return valueOf(result);
}
/**
@@ -2322,27 +2343,25 @@
* (Computes {@code (this==0? -1 : log2(this & -this))}.)
*
* @return index of the rightmost one bit in this BigInteger.
*/
public int getLowestSetBit() {
- /*
- * Initialize lowestSetBit field the first time this method is
- * executed. This method depends on the atomicity of int modifies;
- * without this guarantee, it would have to be synchronized.
- */
- if (lowestSetBit == -2) {
+ @SuppressWarnings("deprecation") int lsb = lowestSetBit - 2;
+ if (lsb == -2) { // lowestSetBit not initialized yet
+ lsb = 0;
if (signum == 0) {
- lowestSetBit = -1;
+ lsb -= 1;
} else {
// Search for lowest order nonzero int
int i,b;
for (i=0; (b = getInt(i))==0; i++)
;
- lowestSetBit = (i << 5) + trailingZeroCnt(b);
+ lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
}
+ lowestSetBit = lsb + 2;
}
- return lowestSetBit;
+ return lsb;
}
// Miscellaneous Bit Operations
@@ -2355,145 +2374,63 @@
*
* @return number of bits in the minimal two's-complement
* representation of this BigInteger, <i>excluding</i> a sign bit.
*/
public int bitLength() {
- /*
- * Initialize bitLength field the first time this method is executed.
- * This method depends on the atomicity of int modifies; without
- * this guarantee, it would have to be synchronized.
- */
- if (bitLength == -1) {
- if (signum == 0) {
- bitLength = 0;
+ @SuppressWarnings("deprecation") int n = bitLength - 1;
+ if (n == -1) { // bitLength not initialized yet
+ int[] m = mag;
+ int len = m.length;
+ if (len == 0) {
+ n = 0; // offset by one to initialize
} else {
// Calculate the bit length of the magnitude
- int magBitLength = ((mag.length-1) << 5) + bitLen(mag[0]);
-
+ int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
if (signum < 0) {
// Check if magnitude is a power of two
- boolean pow2 = (bitCnt(mag[0]) == 1);
- for(int i=1; i<mag.length && pow2; i++)
- pow2 = (mag[i]==0);
+ boolean pow2 = (Integer.bitCount(mag[0]) == 1);
+ for(int i=1; i< len && pow2; i++)
+ pow2 = (mag[i] == 0);
- bitLength = (pow2 ? magBitLength-1 : magBitLength);
+ n = (pow2 ? magBitLength -1 : magBitLength);
} else {
- bitLength = magBitLength;
+ n = magBitLength;
}
}
+ bitLength = n + 1;
}
- return bitLength;
+ return n;
}
/**
- * bitLen(val) is the number of bits in val.
- */
- static int bitLen(int w) {
- // Binary search - decision tree (5 tests, rarely 6)
- return
- (w < 1<<15 ?
- (w < 1<<7 ?
- (w < 1<<3 ?
- (w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
- (w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
- (w < 1<<11 ?
- (w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
- (w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
- (w < 1<<23 ?
- (w < 1<<19 ?
- (w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :
- (w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) :
- (w < 1<<27 ?
- (w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) :
- (w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31)))));
- }
-
- /*
- * trailingZeroTable[i] is the number of trailing zero bits in the binary
- * representation of i.
- */
- final static byte trailingZeroTable[] = {
- -25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
- 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
-
- /**
* Returns the number of bits in the two's complement representation
* of this BigInteger that differ from its sign bit. This method is
* useful when implementing bit-vector style sets atop BigIntegers.
*
* @return number of bits in the two's complement representation
* of this BigInteger that differ from its sign bit.
*/
public int bitCount() {
- /*
- * Initialize bitCount field the first time this method is executed.
- * This method depends on the atomicity of int modifies; without
- * this guarantee, it would have to be synchronized.
- */
- if (bitCount == -1) {
+ @SuppressWarnings("deprecation") int bc = bitCount - 1;
+ if (bc == -1) { // bitCount not initialized yet
+ bc = 0; // offset by one to initialize
// Count the bits in the magnitude
- int magBitCount = 0;
for (int i=0; i<mag.length; i++)
- magBitCount += bitCnt(mag[i]);
-
+ bc += Integer.bitCount(mag[i]);
if (signum < 0) {
// Count the trailing zeros in the magnitude
int magTrailingZeroCount = 0, j;
for (j=mag.length-1; mag[j]==0; j--)
magTrailingZeroCount += 32;
- magTrailingZeroCount +=
- trailingZeroCnt(mag[j]);
-
- bitCount = magBitCount + magTrailingZeroCount - 1;
- } else {
- bitCount = magBitCount;
+ magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]);
+ bc += magTrailingZeroCount - 1;
}
+ bitCount = bc + 1;
}
- return bitCount;
+ return bc;
}
- static int bitCnt(int val) {
- val -= (0xaaaaaaaa & val) >>> 1;
- val = (val & 0x33333333) + ((val >>> 2) & 0x33333333);
- val = val + (val >>> 4) & 0x0f0f0f0f;
- val += val >>> 8;
- val += val >>> 16;
- return val & 0xff;
- }
-
- static int trailingZeroCnt(int val) {
- // Loop unrolled for performance
- int byteVal = val & 0xff;
- if (byteVal != 0)
- return trailingZeroTable[byteVal];
-
- byteVal = (val >>> 8) & 0xff;
- if (byteVal != 0)
- return trailingZeroTable[byteVal] + 8;
-
- byteVal = (val >>> 16) & 0xff;
- if (byteVal != 0)
- return trailingZeroTable[byteVal] + 16;
-
- byteVal = (val >>> 24) & 0xff;
- return trailingZeroTable[byteVal] + 24;
- }
-
// Primality Testing
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite. If
@@ -2534,33 +2471,45 @@
* @param val BigInteger to which this BigInteger is to be compared.
* @return -1, 0 or 1 as this BigInteger is numerically less than, equal
* to, or greater than {@code val}.
*/
public int compareTo(BigInteger val) {
- return (signum==val.signum
- ? signum*intArrayCmp(mag, val.mag)
- : (signum>val.signum ? 1 : -1));
+ if (signum == val.signum) {
+ switch (signum) {
+ case 1:
+ return compareMagnitude(val);
+ case -1:
+ return val.compareMagnitude(this);
+ default:
+ return 0;
}
+ }
+ return signum > val.signum ? 1 : -1;
+ }
- /*
- * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
- * less than, equal to, or greater than arg2.
+ /**
+ * Compares the magnitude array of this BigInteger with the specified
+ * BigInteger's. This is the version of compareTo ignoring sign.
+ *
+ * @param val BigInteger whose magnitude array to be compared.
+ * @return -1, 0 or 1 as this magnitude array is less than, equal to or
+ * greater than the magnitude aray for the specified BigInteger's.
*/
- private static int intArrayCmp(int[] arg1, int[] arg2) {
- if (arg1.length < arg2.length)
+ final int compareMagnitude(BigInteger val) {
+ int[] m1 = mag;
+ int len1 = m1.length;
+ int[] m2 = val.mag;
+ int len2 = m2.length;
+ if (len1 < len2)
return -1;
- if (arg1.length > arg2.length)
+ if (len1 > len2)
return 1;
-
- // Argument lengths are equal; compare the values
- for (int i=0; i<arg1.length; i++) {
- long b1 = arg1[i] & LONG_MASK;
- long b2 = arg2[i] & LONG_MASK;
- if (b1 < b2)
- return -1;
- if (b1 > b2)
- return 1;
+ for (int i = 0; i < len1; i++) {
+ int a = m1[i];
+ int b = m2[i];
+ if (a != b)
+ return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
}
return 0;
}
/**
@@ -2575,17 +2524,23 @@
if (x == this)
return true;
if (!(x instanceof BigInteger))
return false;
+
BigInteger xInt = (BigInteger) x;
+ if (xInt.signum != signum)
+ return false;
- if (xInt.signum != signum || xInt.mag.length != mag.length)
+ int[] m = mag;
+ int len = m.length;
+ int[] xm = xInt.mag;
+ if (len != xm.length)
return false;
- for (int i=0; i<mag.length; i++)
- if (xInt.mag[i] != mag[i])
+ for (int i = 0; i < len; i++)
+ if (xm[i] != m[i])
return false;
return true;
}
@@ -2660,16 +2615,15 @@
int numGroups = 0;
while (tmp.signum != 0) {
BigInteger d = longRadix[radix];
MutableBigInteger q = new MutableBigInteger(),
- r = new MutableBigInteger(),
a = new MutableBigInteger(tmp.mag),
b = new MutableBigInteger(d.mag);
- a.divide(b, q, r);
- BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
- BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);
+ MutableBigInteger r = a.divide(b, q);
+ BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
+ BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
tmp = q2;
}
@@ -2834,66 +2788,53 @@
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
private static int[] stripLeadingZeroInts(int val[]) {
- int byteLength = val.length;
+ int vlen = val.length;
int keep;
// Find first nonzero byte
- for (keep=0; keep<val.length && val[keep]==0; keep++)
+ for (keep = 0; keep < vlen && val[keep] == 0; keep++)
;
-
- int result[] = new int[val.length - keep];
- for(int i=0; i<val.length - keep; i++)
- result[i] = val[keep+i];
-
- return result;
+ return java.util.Arrays.copyOfRange(val, keep, vlen);
}
/**
* Returns the input array stripped of any leading zero bytes.
* Since the source is trusted the copying may be skipped.
*/
private static int[] trustedStripLeadingZeroInts(int val[]) {
- int byteLength = val.length;
+ int vlen = val.length;
int keep;
// Find first nonzero byte
- for (keep=0; keep<val.length && val[keep]==0; keep++)
+ for (keep = 0; keep < vlen && val[keep] == 0; keep++)
;
-
- // Only perform copy if necessary
- if (keep > 0) {
- int result[] = new int[val.length - keep];
- for(int i=0; i<val.length - keep; i++)
- result[i] = val[keep+i];
- return result;
+ return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
}
- return val;
- }
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
private static int[] stripLeadingZeroBytes(byte a[]) {
int byteLength = a.length;
int keep;
// Find first nonzero byte
- for (keep=0; keep<a.length && a[keep]==0; keep++)
+ for (keep = 0; keep < byteLength && a[keep]==0; keep++)
;
// Allocate new array and copy relevant part of input array
- int intLength = ((byteLength - keep) + 3)/4;
+ int intLength = ((byteLength - keep) + 3) >>> 2;
int[] result = new int[intLength];
int b = byteLength - 1;
for (int i = intLength-1; i >= 0; i--) {
result[i] = a[b--] & 0xff;
int bytesRemaining = b - keep + 1;
int bytesToTransfer = Math.min(3, bytesRemaining);
- for (int j=8; j <= 8*bytesToTransfer; j += 8)
+ for (int j=8; j <= (bytesToTransfer << 3); j += 8)
result[i] |= ((a[b--] & 0xff) << j);
}
return result;
}
@@ -3035,11 +2976,11 @@
/**
* Returns the length of the two's complement representation in ints,
* including space for at least one sign bit.
*/
private int intLength() {
- return bitLength()/32 + 1;
+ return (bitLength() >>> 5) + 1;
}
/* Returns sign bit */
private int signBit() {
return signum < 0 ? 1 : 0;
@@ -3072,23 +3013,23 @@
* Returns the index of the int that contains the first nonzero int in the
* little-endian binary representation of the magnitude (int 0 is the
* least significant). If the magnitude is zero, return value is undefined.
*/
private int firstNonzeroIntNum() {
- /*
- * Initialize firstNonzeroIntNum field the first time this method is
- * executed. This method depends on the atomicity of int modifies;
- * without this guarantee, it would have to be synchronized.
- */
- if (firstNonzeroIntNum == -2) {
+ int fn = firstNonzeroIntNum - 2;
+ if (fn == -2) { // firstNonzeroIntNum not initialized yet
+ fn = 0;
+
// Search for the first nonzero int
int i;
- for (i=mag.length-1; i>=0 && mag[i]==0; i--)
+ int mlen = mag.length;
+ for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
;
- firstNonzeroIntNum = mag.length-i-1;
+ fn = mlen - i - 1;
+ firstNonzeroIntNum = fn + 2; // offset by two to initialize
}
- return firstNonzeroIntNum;
+ return fn;
}
/** use serialVersionUID from JDK 1.1. for interoperability */
private static final long serialVersionUID = -8287574255936472291L;
@@ -3119,10 +3060,16 @@
/**
* Reconstitute the {@code BigInteger} instance from a stream (that is,
* deserialize it). The magnitude is read in as an array of bytes
* for historical reasons, but it is converted to an array of ints
* and the byte array is discarded.
+ * Note:
+ * The current convention is to initialize the cache fields, bitCount,
+ * bitLength and lowestSetBit, to 0 rather than some other marker value.
+ * Therefore, no explicit action to set these fields needs to be taken in
+ * readObject because those fields already have a 0 value be default since
+ * defaultReadObject is not being used.
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
/*
* In order to maintain compatibility with previous serialized forms,
@@ -3134,35 +3081,50 @@
// prepare to read the alternate persistent fields
ObjectInputStream.GetField fields = s.readFields();
// Read the alternate persistent fields that we care about
- signum = fields.get("signum", -2);
+ int sign = fields.get("signum", -2);
byte[] magnitude = (byte[])fields.get("magnitude", null);
// Validate signum
- if (signum < -1 || signum > 1) {
+ if (sign < -1 || sign > 1) {
String message = "BigInteger: Invalid signum value";
if (fields.defaulted("signum"))
message = "BigInteger: Signum not present in stream";
throw new java.io.StreamCorruptedException(message);
}
- if ((magnitude.length==0) != (signum==0)) {
+ if ((magnitude.length == 0) != (sign == 0)) {
String message = "BigInteger: signum-magnitude mismatch";
if (fields.defaulted("magnitude"))
message = "BigInteger: Magnitude not present in stream";
throw new java.io.StreamCorruptedException(message);
}
- // Set "cached computation" fields to their initial values
- bitCount = bitLength = -1;
- lowestSetBit = firstNonzeroByteNum = firstNonzeroIntNum = -2;
+ // Commit final fields via Unsafe
+ unsafe.putIntVolatile(this, signumOffset, sign);
// Calculate mag field from magnitude and discard magnitude
- mag = stripLeadingZeroBytes(magnitude);
+ unsafe.putObjectVolatile(this, magOffset,
+ stripLeadingZeroBytes(magnitude));
}
+ // Support for resetting final fields while deserializing
+ private static final sun.misc.Unsafe unsafe = sun.misc.Unsafe.getUnsafe();
+ private static final long signumOffset;
+ private static final long magOffset;
+ static {
+ try {
+ signumOffset = unsafe.objectFieldOffset
+ (BigInteger.class.getDeclaredField("signum"));
+ magOffset = unsafe.objectFieldOffset
+ (BigInteger.class.getDeclaredField("mag"));
+ } catch (Exception ex) {
+ throw new Error(ex);
+ }
+ }
+
/**
* Save the {@code BigInteger} instance to a stream.
* The magnitude of a BigInteger is serialized as a byte array for
* historical reasons.
*
@@ -3172,10 +3134,12 @@
private void writeObject(ObjectOutputStream s) throws IOException {
// set the values of the Serializable fields
ObjectOutputStream.PutField fields = s.putFields();
fields.put("signum", signum);
fields.put("magnitude", magSerializedForm());
+ // The values written for cached fields are compatible with older
+ // versions, but are ignored in readObject so don't otherwise matter.
fields.put("bitCount", -1);
fields.put("bitLength", -1);
fields.put("lowestSetBit", -2);
fields.put("firstNonzeroByteNum", -2);
@@ -3185,16 +3149,17 @@
/**
* Returns the mag array as an array of bytes.
*/
private byte[] magSerializedForm() {
- int bitLen = (mag.length == 0 ? 0 :
- ((mag.length - 1) << 5) + bitLen(mag[0]));
- int byteLen = (bitLen + 7)/8;
+ int len = mag.length;
+
+ int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0]));
+ int byteLen = (bitLen + 7) >>> 3;
byte[] result = new byte[byteLen];
- for (int i=byteLen-1, bytesCopied=4, intIndex=mag.length-1, nextInt=0;
+ for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0;
i>=0; i--) {
if (bytesCopied == 4) {
nextInt = mag[intIndex--];
bytesCopied = 1;
} else {