1 /*
2 * Copyright (c) 1996, 2007, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
336 firstGroupLen = digitsPerInt[radix];
337 String group = val.substring(cursor, cursor += firstGroupLen);
338 magnitude[numWords - 1] = Integer.parseInt(group, radix);
339 if (magnitude[numWords - 1] < 0)
340 throw new NumberFormatException("Illegal digit");
341
342 // Process remaining digit groups
343 int superRadix = intRadix[radix];
344 int groupVal = 0;
345 while (cursor < len) {
346 group = val.substring(cursor, cursor += digitsPerInt[radix]);
347 groupVal = Integer.parseInt(group, radix);
348 if (groupVal < 0)
349 throw new NumberFormatException("Illegal digit");
350 destructiveMulAdd(magnitude, superRadix, groupVal);
351 }
352 // Required for cases where the array was overallocated.
353 mag = trustedStripLeadingZeroInts(magnitude);
354 }
355
356 // Constructs a new BigInteger using a char array with radix=10
357 BigInteger(char[] val) {
358 int cursor = 0, numDigits;
359 int len = val.length;
360
361 // Check for leading minus sign
362 int sign = 1;
363 if (val[0] == '-') {
364 if (len == 1)
365 throw new NumberFormatException("Zero length BigInteger");
366 sign = -1;
367 cursor = 1;
368 } else if (val[0] == '+') {
369 if (len == 1)
370 throw new NumberFormatException("Zero length BigInteger");
371 cursor = 1;
372 }
373
374 // Skip leading zeros and compute number of digits in magnitude
375 while (cursor < len && Character.digit(val[cursor], 10) == 0)
376 cursor++;
377 if (cursor == len) {
378 signum = 0;
379 mag = ZERO.mag;
380 return;
381 }
382
383 numDigits = len - cursor;
384 signum = sign;
385
386 // Pre-allocate array of expected size
387 int numWords;
388 if (len < 10) {
389 numWords = 1;
390 } else {
391 int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
392 numWords = (numBits + 31) >>> 5;
393 }
394 int[] magnitude = new int[numWords];
395
396 // Process first (potentially short) digit group
397 int firstGroupLen = numDigits % digitsPerInt[10];
398 if (firstGroupLen == 0)
399 firstGroupLen = digitsPerInt[10];
400 magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen);
401
402 // Process remaining digit groups
403 while (cursor < len) {
404 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
405 destructiveMulAdd(magnitude, intRadix[10], groupVal);
1041 */
1042 public BigInteger add(BigInteger val) {
1043 if (val.signum == 0)
1044 return this;
1045 if (signum == 0)
1046 return val;
1047 if (val.signum == signum)
1048 return new BigInteger(add(mag, val.mag), signum);
1049
1050 int cmp = compareMagnitude(val);
1051 if (cmp == 0)
1052 return ZERO;
1053 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1054 : subtract(val.mag, mag));
1055 resultMag = trustedStripLeadingZeroInts(resultMag);
1056
1057 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1058 }
1059
1060 /**
1061 * Adds the contents of the int arrays x and y. This method allocates
1062 * a new int array to hold the answer and returns a reference to that
1063 * array.
1064 */
1065 private static int[] add(int[] x, int[] y) {
1066 // If x is shorter, swap the two arrays
1067 if (x.length < y.length) {
1068 int[] tmp = x;
1069 x = y;
1070 y = tmp;
1071 }
1072
1073 int xIndex = x.length;
1074 int yIndex = y.length;
1075 int result[] = new int[xIndex];
1076 long sum = 0;
1077
1078 // Add common parts of both numbers
1079 while(yIndex > 0) {
1080 sum = (x[--xIndex] & LONG_MASK) +
1081 (y[--yIndex] & LONG_MASK) + (sum >>> 32);
1082 result[xIndex] = (int)sum;
1083 }
1084
1085 // Copy remainder of longer number while carry propagation is required
1086 boolean carry = (sum >>> 32 != 0);
1087 while (xIndex > 0 && carry)
1088 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1089
1090 // Copy remainder of longer number
1091 while (xIndex > 0)
1092 result[--xIndex] = x[xIndex];
1093
1094 // Grow result if necessary
1095 if (carry) {
1096 int bigger[] = new int[result.length + 1];
1097 System.arraycopy(result, 0, bigger, 1, result.length);
1098 bigger[0] = 0x01;
1099 return bigger;
1100 }
1101 return result;
1102 }
1103
1104 /**
1105 * Returns a BigInteger whose value is {@code (this - val)}.
1106 *
1107 * @param val value to be subtracted from this BigInteger.
1108 * @return {@code this - val}
1109 */
1110 public BigInteger subtract(BigInteger val) {
1111 if (val.signum == 0)
1112 return this;
1113 if (signum == 0)
1114 return val.negate();
1115 if (val.signum != signum)
1116 return new BigInteger(add(mag, val.mag), signum);
1117
1118 int cmp = compareMagnitude(val);
1119 if (cmp == 0)
1120 return ZERO;
1121 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1122 : subtract(val.mag, mag));
1123 resultMag = trustedStripLeadingZeroInts(resultMag);
1148 boolean borrow = (difference >> 32 != 0);
1149 while (bigIndex > 0 && borrow)
1150 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1151
1152 // Copy remainder of longer number
1153 while (bigIndex > 0)
1154 result[--bigIndex] = big[bigIndex];
1155
1156 return result;
1157 }
1158
1159 /**
1160 * Returns a BigInteger whose value is {@code (this * val)}.
1161 *
1162 * @param val value to be multiplied by this BigInteger.
1163 * @return {@code this * val}
1164 */
1165 public BigInteger multiply(BigInteger val) {
1166 if (val.signum == 0 || signum == 0)
1167 return ZERO;
1168
1169 int[] result = multiplyToLen(mag, mag.length,
1170 val.mag, val.mag.length, null);
1171 result = trustedStripLeadingZeroInts(result);
1172 return new BigInteger(result, signum == val.signum ? 1 : -1);
1173 }
1174
1175 /**
1176 * Package private methods used by BigDecimal code to multiply a BigInteger
1177 * with a long. Assumes v is not equal to INFLATED.
1178 */
1179 BigInteger multiply(long v) {
1180 if (v == 0 || signum == 0)
1181 return ZERO;
1182 if (v == BigDecimal.INFLATED)
1183 return multiply(BigInteger.valueOf(v));
1184 int rsign = (v > 0 ? signum : -signum);
1185 if (v < 0)
1186 v = -v;
1187 long dh = v >>> 32; // higher order bits
1188 long dl = v & LONG_MASK; // lower order bits
1189
1190 int xlen = mag.length;
1191 int[] value = mag;
1192 int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
1322
1323 // Shift back up and set low bit
1324 primitiveLeftShift(z, zlen, 1);
1325 z[zlen-1] |= x[len-1] & 1;
1326
1327 return z;
1328 }
1329
1330 /**
1331 * Returns a BigInteger whose value is {@code (this / val)}.
1332 *
1333 * @param val value by which this BigInteger is to be divided.
1334 * @return {@code this / val}
1335 * @throws ArithmeticException if {@code val} is zero.
1336 */
1337 public BigInteger divide(BigInteger val) {
1338 MutableBigInteger q = new MutableBigInteger(),
1339 a = new MutableBigInteger(this.mag),
1340 b = new MutableBigInteger(val.mag);
1341
1342 a.divide(b, q);
1343 return q.toBigInteger(this.signum == val.signum ? 1 : -1);
1344 }
1345
1346 /**
1347 * Returns an array of two BigIntegers containing {@code (this / val)}
1348 * followed by {@code (this % val)}.
1349 *
1350 * @param val value by which this BigInteger is to be divided, and the
1351 * remainder computed.
1352 * @return an array of two BigIntegers: the quotient {@code (this / val)}
1353 * is the initial element, and the remainder {@code (this % val)}
1354 * is the final element.
1355 * @throws ArithmeticException if {@code val} is zero.
1356 */
1357 public BigInteger[] divideAndRemainder(BigInteger val) {
1358 BigInteger[] result = new BigInteger[2];
1359 MutableBigInteger q = new MutableBigInteger(),
1360 a = new MutableBigInteger(this.mag),
1361 b = new MutableBigInteger(val.mag);
1362 MutableBigInteger r = a.divide(b, q);
1363 result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
2052 * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
2053 *
2054 * @param n shift distance, in bits.
2055 * @return {@code this << n}
2056 * @throws ArithmeticException if the shift distance is {@code
2057 * Integer.MIN_VALUE}.
2058 * @see #shiftRight
2059 */
2060 public BigInteger shiftLeft(int n) {
2061 if (signum == 0)
2062 return ZERO;
2063 if (n==0)
2064 return this;
2065 if (n<0) {
2066 if (n == Integer.MIN_VALUE) {
2067 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2068 } else {
2069 return shiftRight(-n);
2070 }
2071 }
2072
2073 int nInts = n >>> 5;
2074 int nBits = n & 0x1f;
2075 int magLen = mag.length;
2076 int newMag[] = null;
2077
2078 if (nBits == 0) {
2079 newMag = new int[magLen + nInts];
2080 for (int i=0; i<magLen; i++)
2081 newMag[i] = mag[i];
2082 } else {
2083 int i = 0;
2084 int nBits2 = 32 - nBits;
2085 int highBits = mag[0] >>> nBits2;
2086 if (highBits != 0) {
2087 newMag = new int[magLen + nInts + 1];
2088 newMag[i++] = highBits;
2089 } else {
2090 newMag = new int[magLen + nInts];
2091 }
2092 int j=0;
2093 while (j < magLen-1)
2094 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
2095 newMag[i] = mag[j] << nBits;
2096 }
2097
2098 return new BigInteger(newMag, signum);
2099 }
2100
2101 /**
2102 * Returns a BigInteger whose value is {@code (this >> n)}. Sign
2103 * extension is performed. The shift distance, {@code n}, may be
2104 * negative, in which case this method performs a left shift.
2105 * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.)
2106 *
2107 * @param n shift distance, in bits.
2108 * @return {@code this >> n}
2109 * @throws ArithmeticException if the shift distance is {@code
2110 * Integer.MIN_VALUE}.
2111 * @see #shiftLeft
2112 */
2113 public BigInteger shiftRight(int n) {
2114 if (n==0)
2115 return this;
2116 if (n<0) {
2117 if (n == Integer.MIN_VALUE) {
2118 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2513 */
2514 final int compareMagnitude(BigInteger val) {
2515 int[] m1 = mag;
2516 int len1 = m1.length;
2517 int[] m2 = val.mag;
2518 int len2 = m2.length;
2519 if (len1 < len2)
2520 return -1;
2521 if (len1 > len2)
2522 return 1;
2523 for (int i = 0; i < len1; i++) {
2524 int a = m1[i];
2525 int b = m2[i];
2526 if (a != b)
2527 return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
2528 }
2529 return 0;
2530 }
2531
2532 /**
2533 * Compares this BigInteger with the specified Object for equality.
2534 *
2535 * @param x Object to which this BigInteger is to be compared.
2536 * @return {@code true} if and only if the specified Object is a
2537 * BigInteger whose value is numerically equal to this BigInteger.
2538 */
2539 public boolean equals(Object x) {
2540 // This test is just an optimization, which may or may not help
2541 if (x == this)
2542 return true;
2543
2544 if (!(x instanceof BigInteger))
2545 return false;
2546
2547 BigInteger xInt = (BigInteger) x;
2548 if (xInt.signum != signum)
2549 return false;
2550
2551 int[] m = mag;
2552 int len = m.length;
|
1 /*
2 * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
336 firstGroupLen = digitsPerInt[radix];
337 String group = val.substring(cursor, cursor += firstGroupLen);
338 magnitude[numWords - 1] = Integer.parseInt(group, radix);
339 if (magnitude[numWords - 1] < 0)
340 throw new NumberFormatException("Illegal digit");
341
342 // Process remaining digit groups
343 int superRadix = intRadix[radix];
344 int groupVal = 0;
345 while (cursor < len) {
346 group = val.substring(cursor, cursor += digitsPerInt[radix]);
347 groupVal = Integer.parseInt(group, radix);
348 if (groupVal < 0)
349 throw new NumberFormatException("Illegal digit");
350 destructiveMulAdd(magnitude, superRadix, groupVal);
351 }
352 // Required for cases where the array was overallocated.
353 mag = trustedStripLeadingZeroInts(magnitude);
354 }
355
356 /*
357 * Constructs a new BigInteger using a char array with radix=10.
358 * Sign is precalculated outside and not allowed in the val.
359 */
360 BigInteger(char[] val, int sign, int len) {
361 int cursor = 0, numDigits;
362
363 // Skip leading zeros and compute number of digits in magnitude
364 while (cursor < len && Character.digit(val[cursor], 10) == 0) {
365 cursor++;
366 }
367 if (cursor == len) {
368 signum = 0;
369 mag = ZERO.mag;
370 return;
371 }
372
373 numDigits = len - cursor;
374 signum = sign;
375 // Pre-allocate array of expected size
376 int numWords;
377 if (len < 10) {
378 numWords = 1;
379 } else {
380 int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
381 numWords = (numBits + 31) >>> 5;
382 }
383 int[] magnitude = new int[numWords];
384
385 // Process first (potentially short) digit group
386 int firstGroupLen = numDigits % digitsPerInt[10];
387 if (firstGroupLen == 0)
388 firstGroupLen = digitsPerInt[10];
389 magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen);
390
391 // Process remaining digit groups
392 while (cursor < len) {
393 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
394 destructiveMulAdd(magnitude, intRadix[10], groupVal);
1030 */
1031 public BigInteger add(BigInteger val) {
1032 if (val.signum == 0)
1033 return this;
1034 if (signum == 0)
1035 return val;
1036 if (val.signum == signum)
1037 return new BigInteger(add(mag, val.mag), signum);
1038
1039 int cmp = compareMagnitude(val);
1040 if (cmp == 0)
1041 return ZERO;
1042 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1043 : subtract(val.mag, mag));
1044 resultMag = trustedStripLeadingZeroInts(resultMag);
1045
1046 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1047 }
1048
1049 /**
1050 * Package private methods used by BigDecimal code to add a BigInteger
1051 * with a long. Assumes val is not equal to INFLATED.
1052 */
1053 BigInteger add(long val) {
1054 if (val == 0)
1055 return this;
1056 if (signum == 0)
1057 return valueOf(val);
1058 if (Long.signum(val) == signum)
1059 return new BigInteger(add(mag, Math.abs(val)), signum);
1060 int cmp = compareMagnitude(val);
1061 if (cmp == 0)
1062 return ZERO;
1063 int[] resultMag = (cmp > 0 ? subtract(mag, Math.abs(val)) : subtract(Math.abs(val), mag));
1064 resultMag = trustedStripLeadingZeroInts(resultMag);
1065 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1066 }
1067
1068 /**
1069 * Adds the contents of the int array x and long value val. This
1070 * method allocates a new int array to hold the answer and returns
1071 * a reference to that array. Assumes x.length > 0 and val is
1072 * non-negative
1073 */
1074 private static int[] add(int[] x, long val) {
1075 int[] y;
1076 long sum = 0;
1077 int xIndex = x.length;
1078 int[] result;
1079 int highWord = (int)(val >>> 32);
1080 if (highWord==0) {
1081 result = new int[xIndex];
1082 sum = (x[--xIndex] & LONG_MASK) + val;
1083 result[xIndex] = (int)sum;
1084 } else {
1085 if (xIndex == 1) {
1086 result = new int[2];
1087 sum = val + (x[0] & LONG_MASK);
1088 result[1] = (int)sum;
1089 result[0] = (int)(sum >>> 32);
1090 return result;
1091 } else {
1092 result = new int[xIndex];
1093 sum = (x[--xIndex] & LONG_MASK) + (val & LONG_MASK);
1094 result[xIndex] = (int)sum;
1095 sum = (x[--xIndex] & LONG_MASK) + (highWord & LONG_MASK) + (sum >>> 32);
1096 result[xIndex] = (int)sum;
1097 }
1098 }
1099 // Copy remainder of longer number while carry propagation is required
1100 boolean carry = (sum >>> 32 != 0);
1101 while (xIndex > 0 && carry)
1102 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1103 // Copy remainder of longer number
1104 while (xIndex > 0)
1105 result[--xIndex] = x[xIndex];
1106 // Grow result if necessary
1107 if (carry) {
1108 int bigger[] = new int[result.length + 1];
1109 System.arraycopy(result, 0, bigger, 1, result.length);
1110 bigger[0] = 0x01;
1111 return bigger;
1112 }
1113 return result;
1114 }
1115
1116 /**
1117 * Adds the contents of the int arrays x and y. This method allocates
1118 * a new int array to hold the answer and returns a reference to that
1119 * array.
1120 */
1121 private static int[] add(int[] x, int[] y) {
1122 // If x is shorter, swap the two arrays
1123 if (x.length < y.length) {
1124 int[] tmp = x;
1125 x = y;
1126 y = tmp;
1127 }
1128
1129 int xIndex = x.length;
1130 int yIndex = y.length;
1131 int result[] = new int[xIndex];
1132 long sum = 0;
1133 if(yIndex==1) {
1134 sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
1135 result[xIndex] = (int)sum;
1136 } else {
1137 // Add common parts of both numbers
1138 while(yIndex > 0) {
1139 sum = (x[--xIndex] & LONG_MASK) +
1140 (y[--yIndex] & LONG_MASK) + (sum >>> 32);
1141 result[xIndex] = (int)sum;
1142 }
1143 }
1144 // Copy remainder of longer number while carry propagation is required
1145 boolean carry = (sum >>> 32 != 0);
1146 while (xIndex > 0 && carry)
1147 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1148
1149 // Copy remainder of longer number
1150 while (xIndex > 0)
1151 result[--xIndex] = x[xIndex];
1152
1153 // Grow result if necessary
1154 if (carry) {
1155 int bigger[] = new int[result.length + 1];
1156 System.arraycopy(result, 0, bigger, 1, result.length);
1157 bigger[0] = 0x01;
1158 return bigger;
1159 }
1160 return result;
1161 }
1162
1163 private static int[] subtract(long val, int[] little) {
1164 int highWord = (int)(val >>> 32);
1165 if (highWord==0) {
1166 int result[] = new int[1];
1167 result[0] = (int)(val - (little[0] & LONG_MASK));
1168 return result;
1169 } else {
1170 int result[] = new int[2];
1171 if(little.length==1) {
1172 long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK);
1173 result[1] = (int)difference;
1174 // Subtract remainder of longer number while borrow propagates
1175 boolean borrow = (difference >> 32 != 0);
1176 if(borrow) {
1177 result[0] = highWord - 1;
1178 } else { // Copy remainder of longer number
1179 result[0] = highWord;
1180 }
1181 return result;
1182 } else { // little.length==2
1183 long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK);
1184 result[1] = (int)difference;
1185 difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32);
1186 result[0] = (int)difference;
1187 return result;
1188 }
1189 }
1190 }
1191
1192 /**
1193 * Subtracts the contents of the second argument (val) from the
1194 * first (big). The first int array (big) must represent a larger number
1195 * than the second. This method allocates the space necessary to hold the
1196 * answer.
1197 * assumes val >= 0
1198 */
1199 private static int[] subtract(int[] big, long val) {
1200 int highWord = (int)(val >>> 32);
1201 int bigIndex = big.length;
1202 int result[] = new int[bigIndex];
1203 long difference = 0;
1204
1205 if (highWord==0) {
1206 difference = (big[--bigIndex] & LONG_MASK) - val;
1207 result[bigIndex] = (int)difference;
1208 } else {
1209 difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK);
1210 result[bigIndex] = (int)difference;
1211 difference = (big[--bigIndex] & LONG_MASK) - (highWord & LONG_MASK) + (difference >> 32);
1212 result[bigIndex] = (int)difference;
1213 }
1214
1215
1216 // Subtract remainder of longer number while borrow propagates
1217 boolean borrow = (difference >> 32 != 0);
1218 while (bigIndex > 0 && borrow)
1219 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1220
1221 // Copy remainder of longer number
1222 while (bigIndex > 0)
1223 result[--bigIndex] = big[bigIndex];
1224
1225 return result;
1226 }
1227
1228 /**
1229 * Returns a BigInteger whose value is {@code (this - val)}.
1230 *
1231 * @param val value to be subtracted from this BigInteger.
1232 * @return {@code this - val}
1233 */
1234 public BigInteger subtract(BigInteger val) {
1235 if (val.signum == 0)
1236 return this;
1237 if (signum == 0)
1238 return val.negate();
1239 if (val.signum != signum)
1240 return new BigInteger(add(mag, val.mag), signum);
1241
1242 int cmp = compareMagnitude(val);
1243 if (cmp == 0)
1244 return ZERO;
1245 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1246 : subtract(val.mag, mag));
1247 resultMag = trustedStripLeadingZeroInts(resultMag);
1272 boolean borrow = (difference >> 32 != 0);
1273 while (bigIndex > 0 && borrow)
1274 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1275
1276 // Copy remainder of longer number
1277 while (bigIndex > 0)
1278 result[--bigIndex] = big[bigIndex];
1279
1280 return result;
1281 }
1282
1283 /**
1284 * Returns a BigInteger whose value is {@code (this * val)}.
1285 *
1286 * @param val value to be multiplied by this BigInteger.
1287 * @return {@code this * val}
1288 */
1289 public BigInteger multiply(BigInteger val) {
1290 if (val.signum == 0 || signum == 0)
1291 return ZERO;
1292 int resultSign = signum == val.signum ? 1 : -1;
1293 if (val.mag.length == 1) {
1294 return multiplyByInt(mag,val.mag[0], resultSign);
1295 }
1296 if(mag.length == 1) {
1297 return multiplyByInt(val.mag,mag[0], resultSign);
1298 }
1299 int[] result = multiplyToLen(mag, mag.length,
1300 val.mag, val.mag.length, null);
1301 result = trustedStripLeadingZeroInts(result);
1302 return new BigInteger(result, resultSign);
1303 }
1304
1305 private static BigInteger multiplyByInt(int[] x, int y, int sign) {
1306 if(Integer.bitCount(y)==1) {
1307 return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign);
1308 }
1309 int xlen = x.length;
1310 int[] rmag = new int[xlen + 1];
1311 long carry = 0;
1312 long yl = y & LONG_MASK;
1313 int rstart = rmag.length - 1;
1314 for (int i = xlen - 1; i >= 0; i--) {
1315 long product = (x[i] & LONG_MASK) * yl + carry;
1316 rmag[rstart--] = (int)product;
1317 carry = product >>> 32;
1318 }
1319 if (carry == 0L) {
1320 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
1321 } else {
1322 rmag[rstart] = (int)carry;
1323 }
1324 return new BigInteger(rmag, sign);
1325 }
1326
1327 /**
1328 * Package private methods used by BigDecimal code to multiply a BigInteger
1329 * with a long. Assumes v is not equal to INFLATED.
1330 */
1331 BigInteger multiply(long v) {
1332 if (v == 0 || signum == 0)
1333 return ZERO;
1334 if (v == BigDecimal.INFLATED)
1335 return multiply(BigInteger.valueOf(v));
1336 int rsign = (v > 0 ? signum : -signum);
1337 if (v < 0)
1338 v = -v;
1339 long dh = v >>> 32; // higher order bits
1340 long dl = v & LONG_MASK; // lower order bits
1341
1342 int xlen = mag.length;
1343 int[] value = mag;
1344 int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
1474
1475 // Shift back up and set low bit
1476 primitiveLeftShift(z, zlen, 1);
1477 z[zlen-1] |= x[len-1] & 1;
1478
1479 return z;
1480 }
1481
1482 /**
1483 * Returns a BigInteger whose value is {@code (this / val)}.
1484 *
1485 * @param val value by which this BigInteger is to be divided.
1486 * @return {@code this / val}
1487 * @throws ArithmeticException if {@code val} is zero.
1488 */
1489 public BigInteger divide(BigInteger val) {
1490 MutableBigInteger q = new MutableBigInteger(),
1491 a = new MutableBigInteger(this.mag),
1492 b = new MutableBigInteger(val.mag);
1493
1494 a.divide(b, q, false);
1495 return q.toBigInteger(this.signum * val.signum);
1496 }
1497
1498 /**
1499 * Returns an array of two BigIntegers containing {@code (this / val)}
1500 * followed by {@code (this % val)}.
1501 *
1502 * @param val value by which this BigInteger is to be divided, and the
1503 * remainder computed.
1504 * @return an array of two BigIntegers: the quotient {@code (this / val)}
1505 * is the initial element, and the remainder {@code (this % val)}
1506 * is the final element.
1507 * @throws ArithmeticException if {@code val} is zero.
1508 */
1509 public BigInteger[] divideAndRemainder(BigInteger val) {
1510 BigInteger[] result = new BigInteger[2];
1511 MutableBigInteger q = new MutableBigInteger(),
1512 a = new MutableBigInteger(this.mag),
1513 b = new MutableBigInteger(val.mag);
1514 MutableBigInteger r = a.divide(b, q);
1515 result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
2204 * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
2205 *
2206 * @param n shift distance, in bits.
2207 * @return {@code this << n}
2208 * @throws ArithmeticException if the shift distance is {@code
2209 * Integer.MIN_VALUE}.
2210 * @see #shiftRight
2211 */
2212 public BigInteger shiftLeft(int n) {
2213 if (signum == 0)
2214 return ZERO;
2215 if (n==0)
2216 return this;
2217 if (n<0) {
2218 if (n == Integer.MIN_VALUE) {
2219 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2220 } else {
2221 return shiftRight(-n);
2222 }
2223 }
2224 int[] newMag = shiftLeft(mag,n);
2225
2226 return new BigInteger(newMag, signum);
2227 }
2228
2229 private static int[] shiftLeft(int[] mag, int n) {
2230 int nInts = n >>> 5;
2231 int nBits = n & 0x1f;
2232 int magLen = mag.length;
2233 int newMag[] = null;
2234
2235 if (nBits == 0) {
2236 newMag = new int[magLen + nInts];
2237 for (int i=0; i<magLen; i++)
2238 newMag[i] = mag[i];
2239 } else {
2240 int i = 0;
2241 int nBits2 = 32 - nBits;
2242 int highBits = mag[0] >>> nBits2;
2243 if (highBits != 0) {
2244 newMag = new int[magLen + nInts + 1];
2245 newMag[i++] = highBits;
2246 } else {
2247 newMag = new int[magLen + nInts];
2248 }
2249 int j=0;
2250 while (j < magLen-1)
2251 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
2252 newMag[i] = mag[j] << nBits;
2253 }
2254 return newMag;
2255 }
2256
2257 /**
2258 * Returns a BigInteger whose value is {@code (this >> n)}. Sign
2259 * extension is performed. The shift distance, {@code n}, may be
2260 * negative, in which case this method performs a left shift.
2261 * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.)
2262 *
2263 * @param n shift distance, in bits.
2264 * @return {@code this >> n}
2265 * @throws ArithmeticException if the shift distance is {@code
2266 * Integer.MIN_VALUE}.
2267 * @see #shiftLeft
2268 */
2269 public BigInteger shiftRight(int n) {
2270 if (n==0)
2271 return this;
2272 if (n<0) {
2273 if (n == Integer.MIN_VALUE) {
2274 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2669 */
2670 final int compareMagnitude(BigInteger val) {
2671 int[] m1 = mag;
2672 int len1 = m1.length;
2673 int[] m2 = val.mag;
2674 int len2 = m2.length;
2675 if (len1 < len2)
2676 return -1;
2677 if (len1 > len2)
2678 return 1;
2679 for (int i = 0; i < len1; i++) {
2680 int a = m1[i];
2681 int b = m2[i];
2682 if (a != b)
2683 return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
2684 }
2685 return 0;
2686 }
2687
2688 /**
2689 * Version of compareMagnitude that compares magnitude with long value.
2690 * val can't be Long.MIN_VALUE.
2691 */
2692 final int compareMagnitude(long val) {
2693 assert val != Long.MIN_VALUE;
2694 int[] m1 = mag;
2695 int len = m1.length;
2696 if(len > 2) {
2697 return 1;
2698 }
2699 if (val < 0) {
2700 val = -val;
2701 }
2702 int highWord = (int)(val >>> 32);
2703 if (highWord==0) {
2704 if (len < 1)
2705 return -1;
2706 if (len > 1)
2707 return 1;
2708 int a = m1[0];
2709 int b = (int)val;
2710 if (a != b) {
2711 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1;
2712 }
2713 return 0;
2714 } else {
2715 if (len < 2)
2716 return -1;
2717 int a = m1[0];
2718 int b = highWord;
2719 if (a != b) {
2720 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1;
2721 }
2722 a = m1[1];
2723 b = (int)val;
2724 if (a != b) {
2725 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1;
2726 }
2727 return 0;
2728 }
2729 }
2730
2731 /**
2732 * Compares this BigInteger with the specified Object for equality.
2733 *
2734 * @param x Object to which this BigInteger is to be compared.
2735 * @return {@code true} if and only if the specified Object is a
2736 * BigInteger whose value is numerically equal to this BigInteger.
2737 */
2738 public boolean equals(Object x) {
2739 // This test is just an optimization, which may or may not help
2740 if (x == this)
2741 return true;
2742
2743 if (!(x instanceof BigInteger))
2744 return false;
2745
2746 BigInteger xInt = (BigInteger) x;
2747 if (xInt.signum != signum)
2748 return false;
2749
2750 int[] m = mag;
2751 int len = m.length;
|