biginteger.java

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

    // number of bits in mantissa, including the leading one.
    // 53 unless it's denormalized
    int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);

    // Get top ml + 1 bits.  The extra one is for rounding.
    long m;
    int excess_bits = il - (ml + 1);
    if (excess_bits > 0)
      m = ((words == null) ? ival >> excess_bits
	   : MPN.rshift_long(words, ival, excess_bits));
    else
      m = longValue() << (- excess_bits);

    // Special rounding for maxval.  If the number exceeds maxval by
    // any amount, even if it's less than half a step, it overflows.
    if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
      {
	if (remainder || checkBits(il - ml))
	  return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
	else
	  return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
      }

    // Normal round-to-even rule: round up if the bit dropped is a one, and
    // the bit above it or any of the bits below it is a one.
    if ((m & 1) == 1
	&& ((m & 2) == 2 || remainder || checkBits(excess_bits)))
      {
	m += 2;
	// Check if we overflowed the mantissa
	if ((m & (1L << 54)) != 0)
	  {
	    exp++;
	    // renormalize
	    m >>= 1;
	  }
	// Check if a denormalized mantissa was just rounded up to a
	// normalized one.
	else if (ml == 52 && (m & (1L << 53)) != 0)
	  exp++;
      }
	
    // Discard the rounding bit
    m >>= 1;

    long bits_sign = neg ? (1L << 63) : 0;
    exp += 1023;
    long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
    long bits_mant = m & ~(1L << 52);
    return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
  }

  /** Copy the abolute value of this into an array of words.
   * Assumes words.length >= (this.words == null ? 1 : this.ival).
   * Result is zero-extended, but need not be a valid 2's complement number.
   */
  private void getAbsolute(int[] words)
  {
    int len;
    if (this.words == null)
      {
	len = 1;
	words[0] = this.ival;
      }
    else
      {
	len = this.ival;
	for (int i = len;  --i >= 0; )
	  words[i] = this.words[i];
      }
    if (words[len - 1] < 0)
      negate(words, words, len);
    for (int i = words.length;  --i > len; )
      words[i] = 0;
  }

  /** Set dest[0:len-1] to the negation of src[0:len-1].
   * Return true if overflow (i.e. if src is -2**(32*len-1)).
   * Ok for src==dest. */
  private static boolean negate(int[] dest, int[] src, int len)
  {
    long carry = 1;
    boolean negative = src[len-1] < 0;
    for (int i = 0;  i < len;  i++)
      {
        carry += ((long) (~src[i]) & 0xffffffffL);
        dest[i] = (int) carry;
        carry >>= 32;
      }
    return (negative && dest[len-1] < 0);
  }

  /** Destructively set this to the negative of x.
   * It is OK if x==this.*/
  private void setNegative(BigInteger x)
  {
    int len = x.ival;
    if (x.words == null)
      {
	if (len == Integer.MIN_VALUE)
	  set(- (long) len);
	else
	  set(-len);
	return;
      }
    realloc(len + 1);
    if (negate(words, x.words, len))
      words[len++] = 0;
    ival = len;
  }

  /** Destructively negate this. */
  private final void setNegative()
  {
    setNegative(this);
  }

  private static BigInteger abs(BigInteger x)
  {
    return x.isNegative() ? neg(x) : x;
  }

  public BigInteger abs()
  {
    return abs(this);
  }

  private static BigInteger neg(BigInteger x)
  {
    if (x.words == null && x.ival != Integer.MIN_VALUE)
      return valueOf(- x.ival);
    BigInteger result = new BigInteger(0);
    result.setNegative(x);
    return result.canonicalize();
  }

  public BigInteger negate()
  {
    return neg(this);
  }

  /** Calculates ceiling(log2(this < 0 ? -this : this+1))
   * See Common Lisp: the Language, 2nd ed, p. 361.
   */
  public int bitLength()
  {
    if (words == null)
      return MPN.intLength(ival);
      return MPN.intLength(words, ival);
  }

  public byte[] toByteArray()
  {
    // Determine number of bytes needed.  The method bitlength returns
    // the size without the sign bit, so add one bit for that and then
    // add 7 more to emulate the ceil function using integer math.
    byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
    int nbytes = bytes.length;

    int wptr = 0;
    int word;

    // Deal with words array until one word or less is left to process.
    // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
    while (nbytes > 4)
      {
	word = words[wptr++];
	for (int i = 4; i > 0; --i, word >>= 8)
          bytes[--nbytes] = (byte) word;
      }

    // Deal with the last few bytes.  If BigInteger is an int, use ival.
    word = (words == null) ? ival : words[wptr];
    for ( ; nbytes > 0; word >>= 8)
      bytes[--nbytes] = (byte) word;

    return bytes;
  }

  /** Return the boolean opcode (for bitOp) for swapped operands.
   * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
   */
  private static int swappedOp(int op)
  {
    return
    "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
    .charAt(op);
  }

  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
  private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
  {
    switch (op)
      {
        case 0:  return ZERO;
        case 1:  return x.and(y);
        case 3:  return x;
        case 5:  return y;
        case 15: return valueOf(-1);
      }
    BigInteger result = new BigInteger();
    setBitOp(result, op, x, y);
    return result.canonicalize();
  }

  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
  private static void setBitOp(BigInteger result, int op,
			       BigInteger x, BigInteger y)
  {
    if (y.words == null) ;
    else if (x.words == null || x.ival < y.ival)
      {
	BigInteger temp = x;  x = y;  y = temp;
	op = swappedOp(op);
      }
    int xi;
    int yi;
    int xlen, ylen;
    if (y.words == null)
      {
	yi = y.ival;
	ylen = 1;
      }
    else
      {
	yi = y.words[0];
	ylen = y.ival;
      }
    if (x.words == null)
      {
	xi = x.ival;
	xlen = 1;
      }
    else
      {
	xi = x.words[0];
	xlen = x.ival;
      }
    if (xlen > 1)
      result.realloc(xlen);
    int[] w = result.words;
    int i = 0;
    // Code for how to handle the remainder of x.
    // 0:  Truncate to length of y.
    // 1:  Copy rest of x.
    // 2:  Invert rest of x.
    int finish = 0;
    int ni;
    switch (op)
      {
      case 0:  // clr
	ni = 0;
	break;
      case 1: // and
	for (;;)
	  {
	    ni = xi & yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 1;
	break;
      case 2: // andc2
	for (;;)
	  {
	    ni = xi & ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 1;
	break;
      case 3:  // copy x
	ni = xi;
	finish = 1;  // Copy rest
	break;
      case 4: // andc1
	for (;;)
	  {
	    ni = ~xi & yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 2;
	break;
      case 5: // copy y
	for (;;)
	  {
	    ni = yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	break;
      case 6:  // xor
	for (;;)
	  {
	    ni = xi ^ yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	finish = yi < 0 ? 2 : 1;
	break;
      case 7:  // ior
	for (;;)
	  {
	    ni = xi | yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 1;
	break;
      case 8:  // nor
	for (;;)
	  {
	    ni = ~(xi | yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0)  finish = 2;
	break;
      case 9:  // eqv [exclusive nor]
	for (;;)
	  {
	    ni = ~(xi ^ yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	finish = yi >= 0 ? 2 : 1;
	break;
      case 10:  // c2
	for (;;)
	  {
	    ni = ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	break;
      case 11:  // orc2
	for (;;)
	  {
	    ni = xi | ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0)  finish = 1;
	break;
      case 12:  // c1
	ni = ~xi;
	finish = 2;
	break;
      case 13:  // orc1
	for (;;)
	  {
	    ni = ~xi | yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 2;
	break;
      case 14:  // nand
	for (;;)
	  {
	    ni = ~(xi & yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 2;
	break;
      default:
      case 15:  // set
	ni = -1;
	break;
      }
    // Here i==ylen-1; w[0]..w[i-1] have the correct result;
    // and ni contains the correct result for w[i+1].
    if (i+1 == xlen)
      finish = 0;
    switch (finish)
      {
      case 0:
	if (i == 0 && w == null)
	  {
	    result.ival = ni;
	    return;
	  }
	w[i++] = ni;
	break;
      case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
      case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
      }
    result.ival = i;
  }

  /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
  private static BigInteger and(BigInteger x, int y)
  {
    if (x.words == null)
      return valueOf(x.ival & y);
    if (y >= 0)
      return valueOf(x.words[0] & y);
    int len = x.ival;
    int[] words = new int[len];
    words[0] = x.words[0] & y;
    while (--len > 0)
      words[len] = x.words[len];
    return make(words, x.ival);
  }

  /** Return the logical (bit-wise) "and" of two BigIntegers. */
  public BigInteger and(BigInteger y)
  {
    if (y.words == null)
      return and(this, y.ival);
    else if (words == null)
      return and(y, ival);

    BigInteger x = this;
    if (ival < y.ival)
      {
        BigInteger temp = this;  x = y;  y = temp;
      }
    int i;
    int len = y.isNegative() ? x.ival : y.ival;
    int[] words = new int[len];
    for (i = 0;  i < y.ival;  i++)
      words[i] = x.words[i] & y.words[i];
    for ( ; i < len;  i++)
      words[i] = x.words[i];
    return make(words, len);
  }

  /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
  public BigInteger or(BigInteger y)
  {
    return bitOp(7, this, y);
  }

  /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
  public BigInteger xor(BigInteger y)
  {
    return bitOp(6, this, y);
  }

  /** Return the logical (bit-wise) negation of a BigInteger. */
  public BigInteger not()
  {
    return bitOp(12, this, ZERO);
  }

  public BigInteger andNot(BigInteger val)
  {
    return and(val.not());
  }

  public BigInteger clearBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return and(ONE.shiftLeft(n).not());
  }

  public BigInteger setBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return or(ONE.shiftLeft(n));
  }

  public boolean testBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return !and(ONE.shiftLeft(n)).isZero();
  }

  public BigInteger flipBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return xor(ONE.shiftLeft(n));
  }

  public int getLowestSetBit()
  {
    if (isZero())
      return -1;

    if (words == null)
      return MPN.findLowestBit(ival);
    else
      return MPN.findLowestBit(words);
  }

  // bit4count[I] is number of '1' bits in I.
  private static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
					     1, 2, 2, 3,  2, 3, 3, 4};

  private static int bitCount(int i)
  {
    int count = 0;
    while (i != 0)
      {
	count += bit4_count[i & 15];
	i >>>= 4;
      }
    return count;
  }

  private static int bitCount(int[] x, int len)
  {
    int count = 0;
    while (--len >= 0)
      count += bitCount(x[len]);
    return count;
  }

  /** Count one bits in a BigInteger.
   * If argument is negative, count zero bits instead. */
  public int bitCount()
  {
    int i, x_len;
    int[] x_words = words;
    if (x_words == null)
      {
	x_len = 1;
	i = bitCount(ival);
      }
    else
      {
	x_len = ival;
	i = bitCount(x_words, x_len);
      }
    return isNegative() ? x_len * 32 - i : i;
  }

  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    s.defaultReadObject();
    words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
    BigInteger result = make(words, words.length);
    this.ival = result.ival;
    this.words = result.words;
  }

  private void writeObject(ObjectOutputStream s)
    throws IOException, ClassNotFoundException
  {
    signum = signum();
    magnitude = toByteArray();
    s.defaultWriteObject();
  }
}