1 /* java.math.BigInteger -- Arbitary precision integers
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
41 import gnu.java.math.MPN;
43 import java.io.IOException;
44 import java.io.ObjectInputStream;
45 import java.io.ObjectOutputStream;
46 import java.util.Random;
49 * Written using on-line Java Platform 1.2 API Specification, as well
50 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
51 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
53 * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
54 * (found in Kawa 1.6.62).
56 * @author Warren Levy (warrenl@cygnus.com)
57 * @date December 20, 1999.
58 * @status believed complete and correct.
60 public class BigInteger extends Number implements Comparable<BigInteger>
62 /** All integers are stored in 2's-complement form.
63 * If words == null, the ival is the value of this BigInteger.
64 * Otherwise, the first ival elements of words make the value
65 * of this BigInteger, stored in little-endian order, 2's-complement form. */
66 private transient int ival;
67 private transient int[] words;
69 // Serialization fields.
70 private int bitCount = -1;
71 private int bitLength = -1;
72 private int firstNonzeroByteNum = -2;
73 private int lowestSetBit = -2;
74 private byte[] magnitude;
76 private static final long serialVersionUID = -8287574255936472291L;
79 /** We pre-allocate integers in the range minFixNum..maxFixNum.
80 * Note that we must at least preallocate 0, 1, and 10. */
81 private static final int minFixNum = -100;
82 private static final int maxFixNum = 1024;
83 private static final int numFixNum = maxFixNum-minFixNum+1;
84 private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];
88 for (int i = numFixNum; --i >= 0; )
89 smallFixNums[i] = new BigInteger(i + minFixNum);
93 * The constant zero as a BigInteger.
96 public static final BigInteger ZERO = smallFixNums[0 - minFixNum];
99 * The constant one as a BigInteger.
102 public static final BigInteger ONE = smallFixNums[1 - minFixNum];
105 * The constant ten as a BigInteger.
108 public static final BigInteger TEN = smallFixNums[10 - minFixNum];
110 /* Rounding modes: */
111 private static final int FLOOR = 1;
112 private static final int CEILING = 2;
113 private static final int TRUNCATE = 3;
114 private static final int ROUND = 4;
116 /** When checking the probability of primes, it is most efficient to
117 * first check the factoring of small primes, so we'll use this array.
119 private static final int[] primes =
120 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
121 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
122 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
123 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
125 /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
126 private static final int[] k =
127 {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
128 private static final int[] t =
129 { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
135 /* Create a new (non-shared) BigInteger, and initialize to an int. */
136 private BigInteger(int value)
141 public BigInteger(String val, int radix)
143 BigInteger result = valueOf(val, radix);
144 this.ival = result.ival;
145 this.words = result.words;
148 public BigInteger(String val)
153 /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
154 public BigInteger(byte[] val)
156 if (val == null || val.length < 1)
157 throw new NumberFormatException();
159 words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
160 BigInteger result = make(words, words.length);
161 this.ival = result.ival;
162 this.words = result.words;
165 public BigInteger(int signum, byte[] magnitude)
167 if (magnitude == null || signum > 1 || signum < -1)
168 throw new NumberFormatException();
173 for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
176 throw new NumberFormatException();
180 // Magnitude is always positive, so don't ever pass a sign of -1.
181 words = byteArrayToIntArray(magnitude, 0);
182 BigInteger result = make(words, words.length);
183 this.ival = result.ival;
184 this.words = result.words;
190 public BigInteger(int numBits, Random rnd)
193 throw new IllegalArgumentException();
198 private void init(int numBits, Random rnd)
200 int highbits = numBits & 31;
201 // minimum number of bytes to store the above number of bits
202 int highBitByteCount = (highbits + 7) / 8;
203 // number of bits to discard from the last byte
204 int discardedBitCount = highbits % 8;
205 if (discardedBitCount != 0)
206 discardedBitCount = 8 - discardedBitCount;
207 byte[] highBitBytes = new byte[highBitByteCount];
210 rnd.nextBytes(highBitBytes);
211 highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
212 for (int i = highBitByteCount - 2; i >= 0; i--)
213 highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
215 int nwords = numBits / 32;
217 while (highbits == 0 && nwords > 0)
219 highbits = rnd.nextInt();
222 if (nwords == 0 && highbits >= 0)
228 ival = highbits < 0 ? nwords + 2 : nwords + 1;
229 words = new int[ival];
230 words[nwords] = highbits;
231 while (--nwords >= 0)
232 words[nwords] = rnd.nextInt();
236 public BigInteger(int bitLength, int certainty, Random rnd)
238 this(bitLength, rnd);
240 // Keep going until we find a probable prime.
244 // ...but first ensure that BI has bitLength bits
245 result = setBit(bitLength - 1);
246 this.ival = result.ival;
247 this.words = result.words;
248 if (isProbablePrime(certainty))
251 init(bitLength, rnd);
256 * Return a BigInteger that is bitLength bits long with a
257 * probability < 2^-100 of being composite.
259 * @param bitLength length in bits of resulting number
260 * @param rnd random number generator to use
261 * @throws ArithmeticException if bitLength < 2
264 public static BigInteger probablePrime(int bitLength, Random rnd)
267 throw new ArithmeticException();
269 return new BigInteger(bitLength, 100, rnd);
272 /** Return a (possibly-shared) BigInteger with a given long value. */
273 public static BigInteger valueOf(long val)
275 if (val >= minFixNum && val <= maxFixNum)
276 return smallFixNums[(int) val - minFixNum];
279 return new BigInteger(i);
280 BigInteger result = alloc(2);
283 result.words[1] = (int)(val >> 32);
287 /** Make a canonicalized BigInteger from an array of words.
288 * The array may be reused (without copying). */
289 private static BigInteger make(int[] words, int len)
293 len = BigInteger.wordsNeeded(words, len);
295 return len == 0 ? ZERO : valueOf(words[0]);
296 BigInteger num = new BigInteger();
302 /** Convert a big-endian byte array to a little-endian array of words. */
303 private static int[] byteArrayToIntArray(byte[] bytes, int sign)
305 // Determine number of words needed.
306 int[] words = new int[bytes.length/4 + 1];
307 int nwords = words.length;
309 // Create a int out of modulo 4 high order bytes.
312 for (int i = bytes.length % 4; i > 0; --i, bptr++)
313 word = (word << 8) | (bytes[bptr] & 0xff);
314 words[--nwords] = word;
316 // Elements remaining in byte[] are a multiple of 4.
318 words[--nwords] = bytes[bptr++] << 24 |
319 (bytes[bptr++] & 0xff) << 16 |
320 (bytes[bptr++] & 0xff) << 8 |
321 (bytes[bptr++] & 0xff);
325 /** Allocate a new non-shared BigInteger.
326 * @param nwords number of words to allocate
328 private static BigInteger alloc(int nwords)
330 BigInteger result = new BigInteger();
332 result.words = new int[nwords];
336 /** Change words.length to nwords.
337 * We allow words.length to be upto nwords+2 without reallocating.
339 private void realloc(int nwords)
350 else if (words == null
351 || words.length < nwords
352 || words.length > nwords + 2)
354 int[] new_words = new int [nwords];
364 System.arraycopy(words, 0, new_words, 0, ival);
370 private boolean isNegative()
372 return (words == null ? ival : words[ival - 1]) < 0;
377 if (ival == 0 && words == null)
379 int top = words == null ? ival : words[ival-1];
380 return top < 0 ? -1 : 1;
383 private static int compareTo(BigInteger x, BigInteger y)
385 if (x.words == null && y.words == null)
386 return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
387 boolean x_negative = x.isNegative();
388 boolean y_negative = y.isNegative();
389 if (x_negative != y_negative)
390 return x_negative ? -1 : 1;
391 int x_len = x.words == null ? 1 : x.ival;
392 int y_len = y.words == null ? 1 : y.ival;
394 return (x_len > y_len) != x_negative ? 1 : -1;
395 return MPN.cmp(x.words, y.words, x_len);
399 public int compareTo(BigInteger val)
401 return compareTo(this, val);
404 public BigInteger min(BigInteger val)
406 return compareTo(this, val) < 0 ? this : val;
409 public BigInteger max(BigInteger val)
411 return compareTo(this, val) > 0 ? this : val;
414 private boolean isZero()
416 return words == null && ival == 0;
419 private boolean isOne()
421 return words == null && ival == 1;
424 /** Calculate how many words are significant in words[0:len-1].
425 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
426 * when words is viewed as a 2's complement integer.
428 private static int wordsNeeded(int[] words, int len)
433 int word = words[--i];
436 while (i > 0 && (word = words[i - 1]) < 0)
439 if (word != -1) break;
444 while (word == 0 && i > 0 && (word = words[i - 1]) >= 0) i--;
450 private BigInteger canonicalize()
453 && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
459 if (words == null && ival >= minFixNum && ival <= maxFixNum)
460 return smallFixNums[ival - minFixNum];
464 /** Add two ints, yielding a BigInteger. */
465 private static BigInteger add(int x, int y)
467 return valueOf((long) x + (long) y);
470 /** Add a BigInteger and an int, yielding a new BigInteger. */
471 private static BigInteger add(BigInteger x, int y)
474 return BigInteger.add(x.ival, y);
475 BigInteger result = new BigInteger(0);
477 return result.canonicalize();
480 /** Set this to the sum of x and y.
482 private void setAdd(BigInteger x, int y)
486 set((long) x.ival + (long) y);
492 for (int i = 0; i < len; i++)
494 carry += ((long) x.words[i] & 0xffffffffL);
495 words[i] = (int) carry;
498 if (x.words[len - 1] < 0)
500 words[len] = (int) carry;
501 ival = wordsNeeded(words, len + 1);
504 /** Destructively add an int to this. */
505 private void setAdd(int y)
510 /** Destructively set the value of this to a long. */
511 private void set(long y)
523 words[1] = (int) (y >> 32);
528 /** Destructively set the value of this to the given words.
529 * The words array is reused, not copied. */
530 private void set(int[] words, int length)
536 /** Destructively set the value of this to that of y. */
537 private void set(BigInteger y)
544 System.arraycopy(y.words, 0, words, 0, y.ival);
549 /** Add two BigIntegers, yielding their sum as another BigInteger. */
550 private static BigInteger add(BigInteger x, BigInteger y, int k)
552 if (x.words == null && y.words == null)
553 return valueOf((long) k * (long) y.ival + (long) x.ival);
557 y = BigInteger.neg(y);
559 y = BigInteger.times(y, valueOf(k));
562 return BigInteger.add(y, x.ival);
564 return BigInteger.add(x, y.ival);
567 { // Swap so x is longer then y.
568 BigInteger tmp = x; x = y; y = tmp;
570 BigInteger result = alloc(x.ival + 1);
572 long carry = MPN.add_n(result.words, x.words, y.words, i);
573 long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
574 for (; i < x.ival; i++)
576 carry += ((long) x.words[i] & 0xffffffffL) + y_ext;
577 result.words[i] = (int) carry;
580 if (x.words[i - 1] < 0)
582 result.words[i] = (int) (carry + y_ext);
584 return result.canonicalize();
587 public BigInteger add(BigInteger val)
589 return add(this, val, 1);
592 public BigInteger subtract(BigInteger val)
594 return add(this, val, -1);
597 private static BigInteger times(BigInteger x, int y)
603 int[] xwords = x.words;
606 return valueOf((long) xlen * (long) y);
608 BigInteger result = BigInteger.alloc(xlen + 1);
609 if (xwords[xlen - 1] < 0)
612 negate(result.words, xwords, xlen);
613 xwords = result.words;
619 negative = !negative;
622 result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
623 result.ival = xlen + 1;
625 result.setNegative();
626 return result.canonicalize();
629 private static BigInteger times(BigInteger x, BigInteger y)
632 return times(x, y.ival);
634 return times(y, x.ival);
635 boolean negative = false;
643 xwords = new int[xlen];
644 negate(xwords, x.words, xlen);
653 negative = !negative;
654 ywords = new int[ylen];
655 negate(ywords, y.words, ylen);
659 // Swap if x is shorter then y.
662 int[] twords = xwords; xwords = ywords; ywords = twords;
663 int tlen = xlen; xlen = ylen; ylen = tlen;
665 BigInteger result = BigInteger.alloc(xlen+ylen);
666 MPN.mul(result.words, xwords, xlen, ywords, ylen);
667 result.ival = xlen+ylen;
669 result.setNegative();
670 return result.canonicalize();
673 public BigInteger multiply(BigInteger y)
675 return times(this, y);
678 private static void divide(long x, long y,
679 BigInteger quotient, BigInteger remainder,
682 boolean xNegative, yNegative;
686 if (x == Long.MIN_VALUE)
688 divide(valueOf(x), valueOf(y),
689 quotient, remainder, rounding_mode);
700 if (y == Long.MIN_VALUE)
702 if (rounding_mode == TRUNCATE)
703 { // x != Long.Min_VALUE implies abs(x) < abs(y)
704 if (quotient != null)
706 if (remainder != null)
710 divide(valueOf(x), valueOf(y),
711 quotient, remainder, rounding_mode);
721 boolean qNegative = xNegative ^ yNegative;
723 boolean add_one = false;
726 switch (rounding_mode)
732 if (qNegative == (rounding_mode == FLOOR))
736 add_one = r > ((y - (q & 1)) >> 1);
740 if (quotient != null)
748 if (remainder != null)
750 // The remainder is by definition: X-Q*Y
753 // Subtract the remainder from Y.
755 // In this case, abs(Q*Y) > abs(X).
756 // So sign(remainder) = -sign(X).
757 xNegative = ! xNegative;
761 // If !add_one, then: abs(Q*Y) <= abs(X).
762 // So sign(remainder) = sign(X).
770 /** Divide two integers, yielding quotient and remainder.
771 * @param x the numerator in the division
772 * @param y the denominator in the division
773 * @param quotient is set to the quotient of the result (iff quotient!=null)
774 * @param remainder is set to the remainder of the result
775 * (iff remainder!=null)
776 * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
778 private static void divide(BigInteger x, BigInteger y,
779 BigInteger quotient, BigInteger remainder,
782 if ((x.words == null || x.ival <= 2)
783 && (y.words == null || y.ival <= 2))
785 long x_l = x.longValue();
786 long y_l = y.longValue();
787 if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
789 divide(x_l, y_l, quotient, remainder, rounding_mode);
794 boolean xNegative = x.isNegative();
795 boolean yNegative = y.isNegative();
796 boolean qNegative = xNegative ^ yNegative;
798 int ylen = y.words == null ? 1 : y.ival;
799 int[] ywords = new int[ylen];
800 y.getAbsolute(ywords);
801 while (ylen > 1 && ywords[ylen - 1] == 0) ylen--;
803 int xlen = x.words == null ? 1 : x.ival;
804 int[] xwords = new int[xlen+2];
805 x.getAbsolute(xwords);
806 while (xlen > 1 && xwords[xlen-1] == 0) xlen--;
810 int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
811 if (cmpval < 0) // abs(x) < abs(y)
812 { // quotient = 0; remainder = num.
813 int[] rwords = xwords; xwords = ywords; ywords = rwords;
814 rlen = xlen; qlen = 1; xwords[0] = 0;
816 else if (cmpval == 0) // abs(x) == abs(y)
818 xwords[0] = 1; qlen = 1; // quotient = 1
819 ywords[0] = 0; rlen = 1; // remainder = 0;
824 // Need to leave room for a word of leading zeros if dividing by 1
825 // and the dividend has the high bit set. It might be safe to
826 // increment qlen in all cases, but it certainly is only necessary
827 // in the following case.
828 if (ywords[0] == 1 && xwords[xlen-1] < 0)
831 ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
833 else // abs(x) > abs(y)
835 // Normalize the denominator, i.e. make its most significant bit set by
836 // shifting it normalization_steps bits to the left. Also shift the
837 // numerator the same number of steps (to keep the quotient the same!).
839 int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
842 // Shift up the denominator setting the most significant bit of
843 // the most significant word.
844 MPN.lshift(ywords, 0, ywords, ylen, nshift);
846 // Shift up the numerator, possibly introducing a new most
848 int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
849 xwords[xlen++] = x_high;
854 MPN.divide(xwords, xlen, ywords, ylen);
856 MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
858 qlen = xlen + 1 - ylen;
859 if (quotient != null)
861 for (int i = 0; i < qlen; i++)
862 xwords[i] = xwords[i+ylen];
866 if (ywords[rlen-1] < 0)
872 // Now the quotient is in xwords, and the remainder is in ywords.
874 boolean add_one = false;
875 if (rlen > 1 || ywords[0] != 0)
876 { // Non-zero remainder i.e. in-exact quotient.
877 switch (rounding_mode)
883 if (qNegative == (rounding_mode == FLOOR))
887 // int cmp = compareTo(remainder<<1, abs(y));
888 BigInteger tmp = remainder == null ? new BigInteger() : remainder;
889 tmp.set(ywords, rlen);
893 int cmp = compareTo(tmp, y);
894 // Now cmp == compareTo(sign(y)*(remainder<<1), y)
897 add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
900 if (quotient != null)
902 quotient.set(xwords, qlen);
905 if (add_one) // -(quotient + 1) == ~(quotient)
906 quotient.setInvert();
908 quotient.setNegative();
913 if (remainder != null)
915 // The remainder is by definition: X-Q*Y
916 remainder.set(ywords, rlen);
919 // Subtract the remainder from Y:
920 // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
925 tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
928 tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
930 // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
931 // Hence, abs(Q*Y) > abs(X).
932 // So sign(remainder) = -sign(X).
934 remainder.setNegative(tmp);
940 // If !add_one, then: abs(Q*Y) <= abs(X).
941 // So sign(remainder) = sign(X).
943 remainder.setNegative();
948 public BigInteger divide(BigInteger val)
951 throw new ArithmeticException("divisor is zero");
953 BigInteger quot = new BigInteger();
954 divide(this, val, quot, null, TRUNCATE);
955 return quot.canonicalize();
958 public BigInteger remainder(BigInteger val)
961 throw new ArithmeticException("divisor is zero");
963 BigInteger rem = new BigInteger();
964 divide(this, val, null, rem, TRUNCATE);
965 return rem.canonicalize();
968 public BigInteger[] divideAndRemainder(BigInteger val)
971 throw new ArithmeticException("divisor is zero");
973 BigInteger[] result = new BigInteger[2];
974 result[0] = new BigInteger();
975 result[1] = new BigInteger();
976 divide(this, val, result[0], result[1], TRUNCATE);
977 result[0].canonicalize();
978 result[1].canonicalize();
982 public BigInteger mod(BigInteger m)
984 if (m.isNegative() || m.isZero())
985 throw new ArithmeticException("non-positive modulus");
987 BigInteger rem = new BigInteger();
988 divide(this, m, null, rem, FLOOR);
989 return rem.canonicalize();
992 /** Calculate the integral power of a BigInteger.
993 * @param exponent the exponent (must be non-negative)
995 public BigInteger pow(int exponent)
1001 throw new ArithmeticException("negative exponent");
1005 int plen = words == null ? 1 : ival; // Length of pow2.
1006 int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
1007 boolean negative = isNegative() && (exponent & 1) != 0;
1008 int[] pow2 = new int [blen];
1009 int[] rwords = new int [blen];
1010 int[] work = new int [blen];
1011 getAbsolute(pow2); // pow2 = abs(this);
1013 rwords[0] = 1; // rwords = 1;
1014 for (;;) // for (i = 0; ; i++)
1016 // pow2 == this**(2**i)
1017 // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
1018 if ((exponent & 1) != 0)
1020 MPN.mul(work, pow2, plen, rwords, rlen);
1021 int[] temp = work; work = rwords; rwords = temp;
1023 while (rwords[rlen - 1] == 0) rlen--;
1029 MPN.mul(work, pow2, plen, pow2, plen);
1030 int[] temp = work; work = pow2; pow2 = temp; // swap to avoid a copy
1032 while (pow2[plen - 1] == 0) plen--;
1034 if (rwords[rlen - 1] < 0)
1037 negate(rwords, rwords, rlen);
1038 return BigInteger.make(rwords, rlen);
1041 private static int[] euclidInv(int a, int b, int prevDiv)
1044 throw new ArithmeticException("not invertible");
1047 // Success: values are indeed invertible!
1048 // Bottom of the recursion reached; start unwinding.
1049 return new int[] { -prevDiv, 1 };
1051 int[] xy = euclidInv(b, a % b, a / b); // Recursion happens here.
1052 a = xy[0]; // use our local copy of 'a' as a work var
1053 xy[0] = a * -prevDiv + xy[1];
1058 private static void euclidInv(BigInteger a, BigInteger b,
1059 BigInteger prevDiv, BigInteger[] xy)
1062 throw new ArithmeticException("not invertible");
1066 // Success: values are indeed invertible!
1067 // Bottom of the recursion reached; start unwinding.
1068 xy[0] = neg(prevDiv);
1073 // Recursion happens in the following conditional!
1075 // If a just contains an int, then use integer math for the rest.
1076 if (a.words == null)
1078 int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1079 xy[0] = new BigInteger(xyInt[0]);
1080 xy[1] = new BigInteger(xyInt[1]);
1084 BigInteger rem = new BigInteger();
1085 BigInteger quot = new BigInteger();
1086 divide(a, b, quot, rem, FLOOR);
1087 // quot and rem may not be in canonical form. ensure
1089 quot.canonicalize();
1090 euclidInv(b, rem, quot, xy);
1093 BigInteger t = xy[0];
1094 xy[0] = add(xy[1], times(t, prevDiv), -1);
1098 public BigInteger modInverse(BigInteger y)
1100 if (y.isNegative() || y.isZero())
1101 throw new ArithmeticException("non-positive modulo");
1103 // Degenerate cases.
1109 // Use Euclid's algorithm as in gcd() but do this recursively
1110 // rather than in a loop so we can use the intermediate results as we
1111 // unwind from the recursion.
1112 // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1113 BigInteger result = new BigInteger();
1114 boolean swapped = false;
1116 if (y.words == null)
1118 // The result is guaranteed to be less than the modulus, y (which is
1119 // an int), so simplify this by working with the int result of this
1120 // modulo y. Also, if this is negative, make it positive via modulo
1121 // math. Note that BigInteger.mod() must be used even if this is
1122 // already an int as the % operator would provide a negative result if
1123 // this is negative, BigInteger.mod() never returns negative values.
1124 int xval = (words != null || isNegative()) ? mod(y).ival : ival;
1127 // Swap values so x > y.
1130 int tmp = xval; xval = yval; yval = tmp;
1133 // Normally, the result is in the 2nd element of the array, but
1134 // if originally x < y, then x and y were swapped and the result
1135 // is in the 1st element of the array.
1137 euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1139 // Result can't be negative, so make it positive by adding the
1140 // original modulus, y.ival (not the possibly "swapped" yval).
1141 if (result.ival < 0)
1142 result.ival += y.ival;
1146 // As above, force this to be a positive value via modulo math.
1147 BigInteger x = isNegative() ? this.mod(y) : this;
1149 // Swap values so x > y.
1150 if (x.compareTo(y) < 0)
1152 result = x; x = y; y = result; // use 'result' as a work var
1155 // As above (for ints), result will be in the 2nd element unless
1156 // the original x and y were swapped.
1157 BigInteger rem = new BigInteger();
1158 BigInteger quot = new BigInteger();
1159 divide(x, y, quot, rem, FLOOR);
1160 // quot and rem may not be in canonical form. ensure
1162 quot.canonicalize();
1163 BigInteger[] xy = new BigInteger[2];
1164 euclidInv(y, rem, quot, xy);
1165 result = swapped ? xy[0] : xy[1];
1167 // Result can't be negative, so make it positive by adding the
1168 // original modulus, y (which is now x if they were swapped).
1169 if (result.isNegative())
1170 result = add(result, swapped ? x : y, 1);
1176 public BigInteger modPow(BigInteger exponent, BigInteger m)
1178 if (m.isNegative() || m.isZero())
1179 throw new ArithmeticException("non-positive modulo");
1181 if (exponent.isNegative())
1182 return modInverse(m).modPow(exponent.negate(), m);
1183 if (exponent.isOne())
1186 // To do this naively by first raising this to the power of exponent
1187 // and then performing modulo m would be extremely expensive, especially
1188 // for very large numbers. The solution is found in Number Theory
1189 // where a combination of partial powers and moduli can be done easily.
1191 // We'll use the algorithm for Additive Chaining which can be found on
1192 // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1194 BigInteger t = this;
1195 BigInteger u = exponent;
1199 if (u.and(ONE).isOne())
1200 s = times(s, t).mod(m);
1201 u = u.shiftRight(1);
1202 t = times(t, t).mod(m);
1208 /** Calculate Greatest Common Divisor for non-negative ints. */
1209 private static int gcd(int a, int b)
1211 // Euclid's algorithm, copied from libg++.
1215 tmp = a; a = b; b = tmp;
1229 public BigInteger gcd(BigInteger y)
1238 && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1244 return valueOf(gcd(xval, yval));
1248 if (y.words == null)
1254 int len = (xval > yval ? xval : yval) + 1;
1255 int[] xwords = new int[len];
1256 int[] ywords = new int[len];
1257 getAbsolute(xwords);
1258 y.getAbsolute(ywords);
1259 len = MPN.gcd(xwords, ywords, len);
1260 BigInteger result = new BigInteger(0);
1262 result.words = xwords;
1263 return result.canonicalize();
1267 * <p>Returns <code>true</code> if this BigInteger is probably prime,
1268 * <code>false</code> if it's definitely composite. If <code>certainty</code>
1269 * is <code><= 0</code>, <code>true</code> is returned.</p>
1271 * @param certainty a measure of the uncertainty that the caller is willing
1272 * to tolerate: if the call returns <code>true</code> the probability that
1273 * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1274 * The execution time of this method is proportional to the value of this
1276 * @return <code>true</code> if this BigInteger is probably prime,
1277 * <code>false</code> if it's definitely composite.
1279 public boolean isProbablePrime(int certainty)
1284 /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1285 * primality test. It is fast, easy and has faster decreasing odds of a
1286 * composite passing than with other tests. This means that this
1287 * method will actually have a probability much greater than the
1288 * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1289 * anyone will complain about better performance with greater certainty.
1291 * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1292 * Cryptography, Second Edition" by Bruce Schneier.
1295 // First rule out small prime factors
1296 BigInteger rem = new BigInteger();
1298 for (i = 0; i < primes.length; i++)
1300 if (words == null && ival == primes[i])
1303 divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
1304 if (rem.canonicalize().isZero())
1308 // Now perform the Rabin-Miller test.
1310 // Set b to the number of times 2 evenly divides (this - 1).
1311 // I.e. 2^b is the largest power of 2 that divides (this - 1).
1312 BigInteger pMinus1 = add(this, -1);
1313 int b = pMinus1.getLowestSetBit();
1315 // Set m such that this = 1 + 2^b * m.
1316 BigInteger m = pMinus1.divide(valueOf(2L).pow(b));
1318 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1319 // 4.49 (controlling the error probability) gives the number of trials
1320 // for an error probability of 1/2**80, given the number of bits in the
1321 // number to test. we shall use these numbers as is if/when 'certainty'
1322 // is less or equal to 80, and twice as much if it's greater.
1323 int bits = this.bitLength();
1324 for (i = 0; i < k.length; i++)
1331 for (int t = 0; t < trials; t++)
1333 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1334 // Remark 4.28 states: "...A strategy that is sometimes employed
1335 // is to fix the bases a to be the first few primes instead of
1336 // choosing them at random.
1337 z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
1338 if (z.isOne() || z.equals(pMinus1))
1339 continue; // Passes the test; may be prime.
1341 for (i = 0; i < b; )
1346 if (z.equals(pMinus1))
1347 break; // Passes the test; may be prime.
1349 z = z.modPow(valueOf(2), this);
1352 if (i == b && !z.equals(pMinus1))
1358 private void setInvert()
1364 for (int i = ival; --i >= 0; )
1365 words[i] = ~words[i];
1369 private void setShiftLeft(BigInteger x, int count)
1373 if (x.words == null)
1377 set((long) x.ival << count);
1380 xwords = new int[1];
1389 int word_count = count >> 5;
1391 int new_len = xlen + word_count;
1395 for (int i = xlen; --i >= 0; )
1396 words[i+word_count] = xwords[i];
1402 int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1404 words[new_len-1] = (shift_out << count) >> count; // sign-extend.
1407 for (int i = word_count; --i >= 0; )
1411 private void setShiftRight(BigInteger x, int count)
1413 if (x.words == null)
1414 set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1415 else if (count == 0)
1419 boolean neg = x.isNegative();
1420 int word_count = count >> 5;
1422 int d_len = x.ival - word_count;
1427 if (words == null || words.length < d_len)
1429 MPN.rshift0 (words, x.words, word_count, d_len, count);
1432 words[d_len-1] |= -2 << (31 - count);
1437 private void setShift(BigInteger x, int count)
1440 setShiftLeft(x, count);
1442 setShiftRight(x, -count);
1445 private static BigInteger shift(BigInteger x, int count)
1447 if (x.words == null)
1450 return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1452 return valueOf((long) x.ival << count);
1456 BigInteger result = new BigInteger(0);
1457 result.setShift(x, count);
1458 return result.canonicalize();
1461 public BigInteger shiftLeft(int n)
1463 return shift(this, n);
1466 public BigInteger shiftRight(int n)
1468 return shift(this, -n);
1471 private void format(int radix, StringBuffer buffer)
1474 buffer.append(Integer.toString(ival, radix));
1476 buffer.append(Long.toString(longValue(), radix));
1479 boolean neg = isNegative();
1481 if (neg || radix != 16)
1483 work = new int[ival];
1494 int buf_start = buffer.length();
1495 for (int i = len; --i >= 0; )
1498 for (int j = 8; --j >= 0; )
1500 int hex_digit = (word >> (4 * j)) & 0xF;
1501 // Suppress leading zeros:
1502 if (hex_digit > 0 || buffer.length() > buf_start)
1503 buffer.append(Character.forDigit(hex_digit, 16));
1509 int i = buffer.length();
1512 int digit = MPN.divmod_1(work, work, len, radix);
1513 buffer.append(Character.forDigit(digit, radix));
1514 while (len > 0 && work[len-1] == 0) len--;
1520 /* Reverse buffer. */
1521 int j = buffer.length() - 1;
1524 char tmp = buffer.charAt(i);
1525 buffer.setCharAt(i, buffer.charAt(j));
1526 buffer.setCharAt(j, tmp);
1533 public String toString()
1535 return toString(10);
1538 public String toString(int radix)
1541 return Integer.toString(ival, radix);
1543 return Long.toString(longValue(), radix);
1544 int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1545 StringBuffer buffer = new StringBuffer(buf_size);
1546 format(radix, buffer);
1547 return buffer.toString();
1550 public int intValue()
1557 public long longValue()
1563 return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1566 public int hashCode()
1568 // FIXME: May not match hashcode of JDK.
1569 return words == null ? ival : (words[0] + words[ival - 1]);
1572 /* Assumes x and y are both canonicalized. */
1573 private static boolean equals(BigInteger x, BigInteger y)
1575 if (x.words == null && y.words == null)
1576 return x.ival == y.ival;
1577 if (x.words == null || y.words == null || x.ival != y.ival)
1579 for (int i = x.ival; --i >= 0; )
1581 if (x.words[i] != y.words[i])
1587 /* Assumes this and obj are both canonicalized. */
1588 public boolean equals(Object obj)
1590 if (! (obj instanceof BigInteger))
1592 return equals(this, (BigInteger) obj);
1595 private static BigInteger valueOf(String s, int radix)
1596 throws NumberFormatException
1598 int len = s.length();
1599 // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
1600 // but slightly more expensive, for little practical gain.
1601 if (len <= 15 && radix <= 16)
1602 return valueOf(Long.parseLong(s, radix));
1607 char ch = s.charAt(0);
1612 bytes = new byte[len - 1];
1618 bytes = new byte[len];
1621 for ( ; i < len; i++)
1624 digit = Character.digit(ch, radix);
1626 throw new NumberFormatException();
1627 bytes[byte_len++] = (byte) digit;
1629 return valueOf(bytes, byte_len, negative, radix);
1632 private static BigInteger valueOf(byte[] digits, int byte_len,
1633 boolean negative, int radix)
1635 int chars_per_word = MPN.chars_per_word(radix);
1636 int[] words = new int[byte_len / chars_per_word + 1];
1637 int size = MPN.set_str(words, digits, byte_len, radix);
1640 if (words[size-1] < 0)
1643 negate(words, words, size);
1644 return make(words, size);
1647 public double doubleValue()
1650 return (double) ival;
1652 return (double) longValue();
1654 return neg(this).roundToDouble(0, true, false);
1655 return roundToDouble(0, false, false);
1658 public float floatValue()
1660 return (float) doubleValue();
1663 /** Return true if any of the lowest n bits are one.
1664 * (false if n is negative). */
1665 private boolean checkBits(int n)
1670 return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1672 for (i = 0; i < (n >> 5) ; i++)
1675 return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1678 /** Convert a semi-processed BigInteger to double.
1679 * Number must be non-negative. Multiplies by a power of two, applies sign,
1680 * and converts to double, with the usual java rounding.
1681 * @param exp power of two, positive or negative, by which to multiply
1682 * @param neg true if negative
1683 * @param remainder true if the BigInteger is the result of a truncating
1684 * division that had non-zero remainder. To ensure proper rounding in
1685 * this case, the BigInteger must have at least 54 bits. */
1686 private double roundToDouble(int exp, boolean neg, boolean remainder)
1689 int il = bitLength();
1691 // Exponent when normalized to have decimal point directly after
1692 // leading one. This is stored excess 1023 in the exponent bit field.
1695 // Gross underflow. If exp == -1075, we let the rounding
1696 // computation determine whether it is minval or 0 (which are just
1697 // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1700 return neg ? -0.0 : 0.0;
1704 return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1706 // number of bits in mantissa, including the leading one.
1707 // 53 unless it's denormalized
1708 int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1710 // Get top ml + 1 bits. The extra one is for rounding.
1712 int excess_bits = il - (ml + 1);
1713 if (excess_bits > 0)
1714 m = ((words == null) ? ival >> excess_bits
1715 : MPN.rshift_long(words, ival, excess_bits));
1717 m = longValue() << (- excess_bits);
1719 // Special rounding for maxval. If the number exceeds maxval by
1720 // any amount, even if it's less than half a step, it overflows.
1721 if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
1723 if (remainder || checkBits(il - ml))
1724 return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1726 return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
1729 // Normal round-to-even rule: round up if the bit dropped is a one, and
1730 // the bit above it or any of the bits below it is a one.
1732 && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
1735 // Check if we overflowed the mantissa
1736 if ((m & (1L << 54)) != 0)
1742 // Check if a denormalized mantissa was just rounded up to a
1744 else if (ml == 52 && (m & (1L << 53)) != 0)
1748 // Discard the rounding bit
1751 long bits_sign = neg ? (1L << 63) : 0;
1753 long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
1754 long bits_mant = m & ~(1L << 52);
1755 return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
1758 /** Copy the abolute value of this into an array of words.
1759 * Assumes words.length >= (this.words == null ? 1 : this.ival).
1760 * Result is zero-extended, but need not be a valid 2's complement number.
1762 private void getAbsolute(int[] words)
1765 if (this.words == null)
1768 words[0] = this.ival;
1773 for (int i = len; --i >= 0; )
1774 words[i] = this.words[i];
1776 if (words[len - 1] < 0)
1777 negate(words, words, len);
1778 for (int i = words.length; --i > len; )
1782 /** Set dest[0:len-1] to the negation of src[0:len-1].
1783 * Return true if overflow (i.e. if src is -2**(32*len-1)).
1784 * Ok for src==dest. */
1785 private static boolean negate(int[] dest, int[] src, int len)
1788 boolean negative = src[len-1] < 0;
1789 for (int i = 0; i < len; i++)
1791 carry += ((long) (~src[i]) & 0xffffffffL);
1792 dest[i] = (int) carry;
1795 return (negative && dest[len-1] < 0);
1798 /** Destructively set this to the negative of x.
1799 * It is OK if x==this.*/
1800 private void setNegative(BigInteger x)
1803 if (x.words == null)
1805 if (len == Integer.MIN_VALUE)
1812 if (negate(words, x.words, len))
1817 /** Destructively negate this. */
1818 private void setNegative()
1823 private static BigInteger abs(BigInteger x)
1825 return x.isNegative() ? neg(x) : x;
1828 public BigInteger abs()
1833 private static BigInteger neg(BigInteger x)
1835 if (x.words == null && x.ival != Integer.MIN_VALUE)
1836 return valueOf(- x.ival);
1837 BigInteger result = new BigInteger(0);
1838 result.setNegative(x);
1839 return result.canonicalize();
1842 public BigInteger negate()
1847 /** Calculates ceiling(log2(this < 0 ? -this : this+1))
1848 * See Common Lisp: the Language, 2nd ed, p. 361.
1850 public int bitLength()
1853 return MPN.intLength(ival);
1854 return MPN.intLength(words, ival);
1857 public byte[] toByteArray()
1859 // Determine number of bytes needed. The method bitlength returns
1860 // the size without the sign bit, so add one bit for that and then
1861 // add 7 more to emulate the ceil function using integer math.
1862 byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
1863 int nbytes = bytes.length;
1868 // Deal with words array until one word or less is left to process.
1869 // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
1872 word = words[wptr++];
1873 for (int i = 4; i > 0; --i, word >>= 8)
1874 bytes[--nbytes] = (byte) word;
1877 // Deal with the last few bytes. If BigInteger is an int, use ival.
1878 word = (words == null) ? ival : words[wptr];
1879 for ( ; nbytes > 0; word >>= 8)
1880 bytes[--nbytes] = (byte) word;
1885 /** Return the boolean opcode (for bitOp) for swapped operands.
1886 * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
1888 private static int swappedOp(int op)
1891 "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1895 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1896 private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
1900 case 0: return ZERO;
1901 case 1: return x.and(y);
1904 case 15: return valueOf(-1);
1906 BigInteger result = new BigInteger();
1907 setBitOp(result, op, x, y);
1908 return result.canonicalize();
1911 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1912 private static void setBitOp(BigInteger result, int op,
1913 BigInteger x, BigInteger y)
1915 if ((y.words != null) && (x.words == null || x.ival < y.ival))
1917 BigInteger temp = x; x = y; y = temp;
1923 if (y.words == null)
1933 if (x.words == null)
1944 result.realloc(xlen);
1945 int[] w = result.words;
1947 // Code for how to handle the remainder of x.
1948 // 0: Truncate to length of y.
1949 // 1: Copy rest of x.
1950 // 2: Invert rest of x.
1962 if (i+1 >= ylen) break;
1963 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1965 if (yi < 0) finish = 1;
1971 if (i+1 >= ylen) break;
1972 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1974 if (yi >= 0) finish = 1;
1978 finish = 1; // Copy rest
1984 if (i+1 >= ylen) break;
1985 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1987 if (yi < 0) finish = 2;
1993 if (i+1 >= ylen) break;
1994 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2001 if (i+1 >= ylen) break;
2002 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2004 finish = yi < 0 ? 2 : 1;
2010 if (i+1 >= ylen) break;
2011 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2013 if (yi >= 0) finish = 1;
2019 if (i+1 >= ylen) break;
2020 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2022 if (yi >= 0) finish = 2;
2024 case 9: // eqv [exclusive nor]
2028 if (i+1 >= ylen) break;
2029 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2031 finish = yi >= 0 ? 2 : 1;
2037 if (i+1 >= ylen) break;
2038 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2045 if (i+1 >= ylen) break;
2046 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2048 if (yi < 0) finish = 1;
2058 if (i+1 >= ylen) break;
2059 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2061 if (yi >= 0) finish = 2;
2067 if (i+1 >= ylen) break;
2068 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2070 if (yi < 0) finish = 2;
2077 // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2078 // and ni contains the correct result for w[i+1].
2084 if (i == 0 && w == null)
2091 case 1: w[i] = ni; while (++i < xlen) w[i] = x.words[i]; break;
2092 case 2: w[i] = ni; while (++i < xlen) w[i] = ~x.words[i]; break;
2097 /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2098 private static BigInteger and(BigInteger x, int y)
2100 if (x.words == null)
2101 return valueOf(x.ival & y);
2103 return valueOf(x.words[0] & y);
2105 int[] words = new int[len];
2106 words[0] = x.words[0] & y;
2108 words[len] = x.words[len];
2109 return make(words, x.ival);
2112 /** Return the logical (bit-wise) "and" of two BigIntegers. */
2113 public BigInteger and(BigInteger y)
2115 if (y.words == null)
2116 return and(this, y.ival);
2117 else if (words == null)
2118 return and(y, ival);
2120 BigInteger x = this;
2123 BigInteger temp = this; x = y; y = temp;
2126 int len = y.isNegative() ? x.ival : y.ival;
2127 int[] words = new int[len];
2128 for (i = 0; i < y.ival; i++)
2129 words[i] = x.words[i] & y.words[i];
2130 for ( ; i < len; i++)
2131 words[i] = x.words[i];
2132 return make(words, len);
2135 /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2136 public BigInteger or(BigInteger y)
2138 return bitOp(7, this, y);
2141 /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2142 public BigInteger xor(BigInteger y)
2144 return bitOp(6, this, y);
2147 /** Return the logical (bit-wise) negation of a BigInteger. */
2148 public BigInteger not()
2150 return bitOp(12, this, ZERO);
2153 public BigInteger andNot(BigInteger val)
2155 return and(val.not());
2158 public BigInteger clearBit(int n)
2161 throw new ArithmeticException();
2163 return and(ONE.shiftLeft(n).not());
2166 public BigInteger setBit(int n)
2169 throw new ArithmeticException();
2171 return or(ONE.shiftLeft(n));
2174 public boolean testBit(int n)
2177 throw new ArithmeticException();
2179 return !and(ONE.shiftLeft(n)).isZero();
2182 public BigInteger flipBit(int n)
2185 throw new ArithmeticException();
2187 return xor(ONE.shiftLeft(n));
2190 public int getLowestSetBit()
2196 return MPN.findLowestBit(ival);
2198 return MPN.findLowestBit(words);
2201 // bit4count[I] is number of '1' bits in I.
2202 private static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3,
2203 1, 2, 2, 3, 2, 3, 3, 4};
2205 private static int bitCount(int i)
2210 count += bit4_count[i & 15];
2216 private static int bitCount(int[] x, int len)
2220 count += bitCount(x[len]);
2224 /** Count one bits in a BigInteger.
2225 * If argument is negative, count zero bits instead. */
2226 public int bitCount()
2229 int[] x_words = words;
2230 if (x_words == null)
2238 i = bitCount(x_words, x_len);
2240 return isNegative() ? x_len * 32 - i : i;
2243 private void readObject(ObjectInputStream s)
2244 throws IOException, ClassNotFoundException
2246 s.defaultReadObject();
2247 if (magnitude.length == 0 || signum == 0)
2254 words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
2255 BigInteger result = make(words, words.length);
2256 this.ival = result.ival;
2257 this.words = result.words;
2261 private void writeObject(ObjectOutputStream s)
2262 throws IOException, ClassNotFoundException
2265 magnitude = signum == 0 ? new byte[0] : toByteArray();
2266 s.defaultWriteObject();