biginteger.java

来自「《移动Agent技术》一书的所有章节源代码。」· Java 代码 · 共 1,801 行 · 第 1/3 页

        w[0] = (int)(u2 + (u1 >> 32) + w[0]);

        return w;
    }

    /**
     * return x with x = y * z - x is assumed to have enough space.
     */
	private int[] multiply(
        int[]   x,
        int[]   y,
        int[]   z)
	{
        for (int i = z.length - 1; i >= 0; i--)
        {
            long    a = z[i] & IMASK;
            long    value = 0;

            for (int j = y.length - 1; j >= 0; j--)
            {
                value += a * (y[j] & IMASK) + (x[i + j + 1] & IMASK);

                x[i + j + 1] = (int)value;

                value >>>= 32;
            }

            x[i] = (int)value;
        }

        return x;
    }

	public BigInteger multiply(
		BigInteger val)
	{
		if (sign == 0 || val.sign == 0) return BigInteger.ZERO;

		int[]   res = new int[magnitude.length + val.magnitude.length];

		return new BigInteger(sign * val.sign, multiply(res, magnitude, val.magnitude));
	}


	public BigInteger negate()
	{
		return new BigInteger(-sign, magnitude);
	}


	public BigInteger pow(
		int exp)
		throws ArithmeticException
	{
		if (exp < 0) throw new ArithmeticException("Negative exponent");
		if (sign == 0) return (exp == 0 ? BigInteger.ONE : this);

		BigInteger y, z;
		y = BigInteger.ONE;
		z = this;

		while (exp != 0)
        {
			if ((exp & 0x1) == 1)
            {
                y = y.multiply(z);
            }
			exp >>= 1;
			if (exp != 0)
            {
                z = z.multiply(z);
            }
        }

		return y;
	}

    /**
     * return x = x % y - done in place (y value preserved)
     */
    private int[] remainder(
        int[]   x,
        int[]   y)
    {
        int xyCmp = compareTo(0, x, 0, y);

        if (xyCmp > 0)
        {
            int[]   c;
            int     shift = bitLength(0, x) - bitLength(0, y);

            if (shift > 1)
            {
                c = shiftLeft(y, shift - 1);
            }
            else
            {
                c = new int[x.length];

                System.arraycopy(y, 0, c, c.length - y.length, y.length);
            }

            subtract(0, x, 0, c);

            int xStart = 0;
            int cStart = 0;

            for (;;)
            {
                int cmp = compareTo(xStart, x, cStart, c);

                while (cmp >= 0)
                {
                    subtract(xStart, x, cStart, c);
                    cmp = compareTo(xStart, x, cStart, c);
                }

                xyCmp = compareTo(xStart, x, 0, y);

                if (xyCmp > 0)
                {
                    if (x[xStart] == 0)
                    {
                        xStart++;
                    }

                    shift = bitLength(cStart, c) - bitLength(xStart, x);

                    if (shift == 0)
                    {
                        c = shiftRightOne(cStart, c);
                    }
                    else
                    {
                        c = shiftRight(cStart, c, shift);
                    }

                    if (c[cStart] == 0)
                    {
                        cStart++;
                    }
                }
                else if (xyCmp == 0)
                {
                    for (int i = xStart; i != x.length; i++)
                    {
                        x[i] = 0;
                    }
                    break;
                }
                else
                {
                    break;
                }
            }
        }
        else if (xyCmp == 0)
        {
            for (int i = 0; i != x.length; i++)
            {
                x[i] = 0;
            }
        }
   
        return x;
    }

	public BigInteger remainder(
		BigInteger val)
		throws ArithmeticException
	{
		if (val.sign == 0)
        {
			throw new ArithmeticException("BigInteger: Divide by zero");
        }

		if (sign == 0)
        {
            return BigInteger.ZERO;
        }

        int[]   res = new int[this.magnitude.length];

        System.arraycopy(this.magnitude, 0, res, 0, res.length);

		return new BigInteger(sign, remainder(res, val.magnitude));
	}

    /**
     * do a left shift - this returns a new array.
     */
    private int[] shiftLeft(
        int[]   mag,
        int     n)
	{
		int nInts = n >>> 5;
		int nBits = n & 0x1f;
		int magLen = mag.length;
		int newMag[] = null;

		if (nBits == 0)
        {
			newMag = new int[magLen + nInts];
			for (int i = 0; i < magLen; i++)
            {
				newMag[i] = mag[i];
            }
        }
        else
        {
            int i = 0;
            int nBits2 = 32 - nBits;
            int highBits = mag[0] >>> nBits2;

            if (highBits != 0)
            {
                newMag = new int[magLen + nInts + 1];
                newMag[i++] = highBits;
            }
            else
            {
                newMag = new int[magLen + nInts];
            }

            int m = mag[0];
            for (int j = 0; j < magLen-1; j++)
            {
                int next = mag[j + 1];

                newMag[i++] = (m << nBits) | (next >>> nBits2);
                m = next;
            }

            newMag[i] = mag[magLen - 1] << nBits;
        }
        
        return newMag;
    }

	public BigInteger shiftLeft(
		int n)
	{
		if (sign == 0 || magnitude.length == 0)
        {
            return ZERO;
        }
		if (n == 0)
        {
            return this;
        }

		if (n < 0)
        {
            return shiftRight(-n);
        }

	    return new BigInteger(sign, shiftLeft(magnitude, n));
	}

    /**
     * do a right shift - this does it in place.
     */
    private int[] shiftRight(
        int     start,
        int[]   mag,
        int     n)
    {
		int nInts = (n >>> 5) + start;
		int nBits = n & 0x1f;
		int magLen = mag.length;

        if (nInts != start)
        {
            for (int i = magLen - 1; i >= nInts; i--)
            {
                mag[i] = mag[i - nInts];
            }
            for (int i = nInts - 1; i >= start; i--)
            {
                mag[i] = 0;
            }
        }

        if (nBits != 0)
        {
            int nBits2 = 32 - nBits;
            int m = mag[magLen - 1];

            for (int i = magLen - 1; i >= nInts + 1; i--)
            {
                int next = mag[i - 1];

                mag[i] = (m >>> nBits) | (next << nBits2);
                m = next;
            }

            mag[nInts] >>>= nBits;
        }

        return mag;
    }

    /**
     * do a right shift by one - this does it in place.
     */
    private int[] shiftRightOne(
        int     start,
        int[]   mag)
    {
		int magLen = mag.length;

        int m = mag[magLen - 1];

        for (int i = magLen - 1; i >= start + 1; i--)
        {
            int next = mag[i - 1];

            mag[i] = (m >>> 1) | (next << 31);
            m = next;
        }

        mag[start] >>>= 1;

        return mag;
    }

	public BigInteger shiftRight(
		int n)
	{
		if (n == 0)
        {
            return this;
        }

		if (n < 0)
        {
            return shiftLeft(-n);
        }

		if (n >= bitLength())
        {
			return (this.sign < 0 ? valueOf(-1) : BigInteger.ZERO);
		}

        int[]   res = new int[this.magnitude.length];
        
        System.arraycopy(this.magnitude, 0, res, 0, res.length);

		return new BigInteger(this.sign, shiftRight(0, res, n));
	}

	public int signum()
	{
		return sign;
	}

    /**
     * returns x = x - y - we assume x is >= y
     */
    private int[] subtract(
        int     xStart,
        int[]   x,
        int     yStart,
        int[]   y)
	{
		int iT = x.length - 1;
		int iV = y.length - 1;
		long m;
		int borrow = 0;

		do
        {
			m = (((long)x[iT]) & IMASK) - (((long)y[iV--]) & IMASK) + borrow;

			x[iT--] = (int)m;

			if (m < 0)
            {
                borrow = -1;
            }
			else
            {
                borrow = 0;
            }
		}
        while (iV >= yStart);

        while (iT >= xStart)
        {
			m = (((long)x[iT]) & IMASK) + borrow;
			x[iT--] = (int)m;

			if (m < 0)
            {
                borrow = -1;
            }
			else
            {
                break;
            }
        }

		return x;
	}

    public BigInteger subtract(
		BigInteger val)
	{
		if (val.sign == 0 || val.magnitude.length == 0)
        {
            return this;
        }
		if (sign == 0 || magnitude.length == 0)
        {
		    return val.negate();
        }
		if (val.sign < 0)
        {
			if (this.sign > 0) return this.add(val.negate());
        }
		else
        {
			if (this.sign < 0) return this.add(val.negate());
        }

		BigInteger bigun, littlun;
		int compare = compareTo(val);
		if (compare == 0)
        {
            return ZERO;
        }

		if (compare < 0)
        {
			bigun = val;
			littlun = this;
        }
		else
        {
			bigun = this;
			littlun = val;
        }

		int res[] = new int[bigun.magnitude.length];

        System.arraycopy(bigun.magnitude, 0, res, 0, res.length);

		return new BigInteger(this.sign * compare, subtract(0, res, 0, littlun.magnitude));
	}

	public byte[] toByteArray()
	{
        int     bitLength = bitLength();
		byte[]  bytes = new byte[bitLength / 8 + 1];

		int bytesCopied = 4;
		int mag = 0;
		int ofs = magnitude.length-1;
		for (int i = bytes.length-1; i >= 0; i--)
        {
			if (bytesCopied == 4 && ofs >= 0)
            {
                if (sign < 0)
                {
				    mag = -magnitude[ofs--];
                }
                else
                {
				    mag = magnitude[ofs--];
                }
				bytesCopied = 1;
            }
			else
            {
				mag >>>= 8;
				bytesCopied++;
            }

			bytes[i] = (byte)mag;
        }

		return bytes;
	}

	public String toString()
	{
		return toString(10);
	}

	public String toString(int rdx)
	{
		// only radix 16 at the moment
		if (magnitude == null)
        {
			return "null";
        }
		else if (sign == 0)
        {
			return "0";
        }

		String s = sign == -1 ? "-" : "";
		String h;
		
		for (int i = 0; i < magnitude.length; i++)
        {
			h = "0000000" + Integer.toHexString(magnitude[i]);
			h = h.substring(h.length()-8);
			s = s + h;
        }

		while (s.length() > 1 && s.charAt(0) == '0') s = s.substring(1);

		if (s.length() == 0) s = "0";

		return s;
	}

	public static final BigInteger ZERO = new BigInteger(0, new byte[0]);
	public static final BigInteger ONE = valueOf(1);
	private static final BigInteger TWO = valueOf(2);


	public static BigInteger valueOf(
		long val)
	{
		if (val == 0)
        {
            return BigInteger.ZERO;
        }

		// store val into a byte array
		byte[] b = new byte[8];
		for (int i = 0; i < 8; i++) {
			b[7 - i] = (byte)val;
			val >>= 8;
			}

		return new BigInteger(b);
	}


	private int max(int a, int b) {
		if (a < b) return b;
		return a;
	}

	public int getLowestSetBit()
	{
        if (this.equals(ZERO))
        {
            return -1;
        }

        int w = magnitude.length - 1;

        while (w >= 0)
        {
            if (magnitude[w] != 0)
            {
                break;
            }

            w--;
        }

        int b = 31;

        while (b > 0)
        {
            if ((magnitude[w] << b) == 0x80000000)
            {
                break;
            }

            b--;
        }

		return (((magnitude.length - 1) - w) * 32 + (31 - b));
	}

	public boolean testBit(
		int n)
		throws ArithmeticException
	{
		if (n < 0) 
        {
            throw new ArithmeticException("Bit position must not be negative");
        }

        if ((n / 32) >= magnitude.length)
        {
            return sign < 0;
        }

		return ((magnitude[(magnitude.length - 1) - n / 32] >> (n % 32)) & 1) > 0;
	}
}