biginteger.java

《移动Agent技术》一书的所有章节源代码。

	return valueOf(result);
    }


    // Single Bit Operations

    /**
     * Returns true iff the designated bit is set. (Computes
     * ((this & (1<<n)) != 0).)  Throws an ArithmeticException if n < 0.
     */
    public boolean testBit(int n) throws ArithmeticException {
	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	return (getByte(n/8) & (1 << (n%8))) != 0;
    }

    /**
     * Returns a BigInteger whose value is equivalent to this number
     * with the designated bit set.  (Computes (this | (1<<n)).)
     * Throws an ArithmeticException if n < 0.
     */
    public BigInteger setBit(int n) throws ArithmeticException {
	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	int byteNum = n/8;
	byte[] result = new byte[Math.max(byteLength(), byteNum+2)];

	for (int i=0; i<result.length; i++)
	    result[result.length-i-1] = getByte(i);

	result[result.length-byteNum-1] |= (1 << (n%8));

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is equivalent to this number
     * with the designated bit cleared. (Computes (this & ~(1<<n)).)
     * Throws an ArithmeticException if n < 0.
     */
    public BigInteger clearBit(int n) throws ArithmeticException {
	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	int byteNum = n/8;
	byte[] result = new byte[Math.max(byteLength(), (n+1)/8+1)];

	for (int i=0; i<result.length; i++)
	    result[result.length-i-1] = getByte(i);

	result[result.length-byteNum-1] &= ~(1 << (n%8));

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is equivalent to this number
     * with the designated bit flipped.  (Computes (this ^ (1<<n)).)
     * Throws an ArithmeticException if n < 0.
     */
    public BigInteger flipBit(int n) throws ArithmeticException {
	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	int byteNum = n/8;
	byte[] result = new byte[Math.max(byteLength(), byteNum+2)];

	for (int i=0; i<result.length; i++)
	    result[result.length-i-1] = getByte(i);

	result[result.length-byteNum-1] ^= (1 << (n%8));

	return valueOf(result);
    }

    /**
     * Returns the index of the rightmost (lowest-order) one bit in this
     * number (i.e., the number of zero bits to the right of the rightmost
     * one bit).  Returns -1 if this number contains no one bits.
     * (Computes (this==0? -1 : log2(this & -this)).)
     */
    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) {
	    if (signum == 0) {
		lowestSetBit = -1;
	    } else {
		/* Search for lowest order nonzero byte */
		int i;
		byte b;
		for (i=0; (b = getByte(i))==0; i++)
		    ;
		lowestSetBit = 8*i + trailingZeroCnt[b & 0xFF];
	    }
	}
	return lowestSetBit;
    }


    // Miscellaneous Bit Operations

    /**
     * Returns the number of bits in the minimal two's-complement
     * representation of this number, *excluding* a sign bit, i.e.,
     * (ceil(log2(this < 0 ? -this : this + 1))).  (For positive
     * numbers, this is equivalent to the number of bits in the
     * ordinary binary representation.)
     */
    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;
	    } else {
		/* Calculate the bit length of the magnitude */
		int magBitLength = 8*(magnitude.length-1)
		    		   + bitLen[magnitude[0] & 0xff];

		if (signum < 0) {
		    /* Check if magnitude is a power of two */
		    boolean pow2 = (bitCnt[magnitude[0]&0xff] == 1);
		    for(int i=1; i<magnitude.length && pow2; i++)
			pow2 = (magnitude[i]==0);

		    bitLength = (pow2 ? magBitLength-1 : magBitLength);
		} else {
		    bitLength = magBitLength;
		}
	    }
	}
	return bitLength;
    }

    /*
     * bitLen[i] is the number of bits in the binary representaion of i.
     */
    private final static byte bitLen[] = {
	0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};

    /**
     * Returns the number of bits in the two's complement representation
     * of this number that differ from its sign bit.  This method is
     * useful when implementing bit-vector style sets atop BigIntegers.
     */
    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) {
	    /* Count the bits in the magnitude */
	    int magBitCount = 0;
	    for (int i=0; i<magnitude.length; i++)
		magBitCount += bitCnt[magnitude[i] & 0xff];

	    if (signum < 0) {
		/* Count the trailing zeros in the magnitude */
		int magTrailingZeroCount = 0, j;
		for (j=magnitude.length-1; magnitude[j]==0; j--)
		    magTrailingZeroCount += 8;
		magTrailingZeroCount += trailingZeroCnt[magnitude[j] & 0xff];

		bitCount = magBitCount + magTrailingZeroCount - 1;
	    } else {
		bitCount = magBitCount;
	    }
	}
	return bitCount;
    }

    /*
     * bitCnt[i] is the number of 1 bits in the binary representation of i.
     */
    private final static byte bitCnt[] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

    /*
     * trailingZeroCnt[i] is the number of trailing zero bits in the binary
     * representaion of i.
     */
    private final static byte trailingZeroCnt[] = {
	8, 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};



    // Primality Testing

    /**
     * Returns true if this BigInteger is probably prime, false if it's
     * definitely composite.  The certainty parameter is a measure
     * of the uncertainty that the caller is willing to tolerate:
     * the method returns true if the probability that this number is
     * is prime exceeds 1 - 1/2**certainty.  The execution time is
     * proportional to the value of the certainty parameter.
     */
    public boolean isProbablePrime(int certainty) {
	/*
	 * This test is taken from the DSA spec.
	 */
	int n = certainty/2;
	if (n <= 0)
	    return true;
	BigInteger w = this.abs();
	if (w.equals(TWO))
	    return true;
	if (!w.testBit(0) || w.equals(ONE))
	    return false;

	/* Find a and m such that m is odd and w == 1 + 2**a * m */
	BigInteger m = w.subtract(ONE);
	int a = m.getLowestSetBit();
	m = m.shiftRight(a);

	/* Do the tests */
	Random rnd = new Random();
	for(int i=0; i<n; i++) {
	    /* Generate a uniform random on (1, w) */
	    BigInteger b;
	    do {
		b = new BigInteger(w.bitLength(), rnd);
	    } while (b.compareTo(ONE) <= 0 || b.compareTo(w) >= 0);

	    int j = 0;
	    BigInteger z = b.modPow(m, w);
	    while(!((j==0 && z.equals(ONE)) || z.equals(w.subtract(ONE)))) {
		if (j>0 && z.equals(ONE) || ++j==a)
		    return false;
		z = z.modPow(TWO, w);
	    }
	}
	return true;
    }


    // Comparison Operations

    /**
     * Returns -1, 0 or 1 as this number is less than, equal to, or
     * greater than val.  This method is provided in preference to
     * individual methods for each of the six boolean comparison operators
     * (<, ==, >, >=, !=, <=).  The suggested idiom for performing these
     * comparisons is:  (x.compareTo(y) <op> 0), where <op> is one of the
     * six comparison operators.
     */
    public int compareTo(BigInteger val) {
	return (signum==val.signum
		? signum*byteArrayCmp(magnitude, val.magnitude)
		: (signum>val.signum ? 1 : -1));
    }

    /*
     * Returns -1, 0 or +1 as big-endian unsigned byte array arg1 is
     * <, == or > arg2.
     */
    private static int byteArrayCmp(byte[] arg1, byte[] arg2) {
	if (arg1.length < arg2.length)
	    return -1;
	if (arg1.length > arg2.length)
	    return 1;

	/* Argument lengths are equal; compare the values */
	for (int i=0; i<arg1.length; i++) {
	    int b1 = arg1[i] & 0xff;
	    int b2 = arg2[i] & 0xff;
	    if (b1 < b2)
		return -1;
	    if (b1 > b2)
		return 1;
	}
	return 0;
    }

    /**
     * Returns true iff x is a BigInteger whose value is equal to this number.
     * This method is provided so that BigIntegers can be used as hash keys.
     */
    public boolean equals(Object x) {
	if (!(x instanceof BigInteger))
	    return false;
	BigInteger xInt = (BigInteger) x;

	if (xInt.signum != signum || xInt.magnitude.length != magnitude.length)
	    return false;

	/* This test is just an optimization, which may or may not help */
	if (xInt == this)
	    return true;

	for (int i=0; i<magnitude.length; i++)
	    if (xInt.magnitude[i] != magnitude[i])
		return false;

	return true;
    }

    /**
     * Returns the BigInteger whose value is the lesser of this and val.
     * If the values are equal, either may be returned.
     */
    public BigInteger min(BigInteger val) {
	return (compareTo(val)<0 ? this : val);
    }

    /**
     * Returns the BigInteger whose value is the greater of this and val.
     * If the values are equal, either may be returned.
     */
    public BigInteger max(BigInteger val) {
	return (compareTo(val)>0 ? this : val);
    }