📄 binaryinteger.java
字号:
// Copy remaining ints of mag
int numInts = (p + 31) / 32;
int[] mag = new int[numInts];
for (int i = 0; i < numInts; i++)
mag[i] = this.mag[i + (this.mag.length - numInts)];
// Mask out any excess bits
int excessBits = (numInts << 5) - p;
mag[0] &= (1L << (32 - excessBits)) - 1;
return (mag[0] == 0 ? new BinaryInteger(1, mag) : new BinaryInteger(
mag, 1));
}
/**
* Returns a BinaryInteger whose value is <tt>(this<sup>-1</sup> mod m)</tt>.
*
* @param m
* the modulus.
* @return <tt>this<sup>-1</sup> mod m</tt>.
* @throws ArithmeticException
* <tt> m <= 0</tt>, or this BinaryInteger has no
* multiplicative inverse mod m (that is, this BinaryInteger is
* not <i>relatively prime</i> to m).
*/
public BinaryInteger modInverse(BinaryInteger m) {
if (m.signum != 1)
throw new ArithmeticException("BinaryInteger: modulus not positive");
if (m.equals(ONE))
return ZERO;
// Calculate (this mod m)
BinaryInteger modVal = this;
if (signum < 0 || (intArrayCmp(mag, m.mag) >= 0))
modVal = this.mod(m);
if (modVal.equals(ONE))
return ONE;
MutableBigInteger a = new MutableBigInteger(modVal);
MutableBigInteger b = new MutableBigInteger(m);
MutableBigInteger result = a.mutableModInverse(b);
return new BinaryInteger(result, 1);
}
// Shift Operations
/**
* 左移运算
*
* @param n
* shift distance, in bits.
* @return <tt>this << n</tt>
* @see #shiftRight
*/
public BinaryInteger shiftLeft(int n) {
if (signum == 0)
return ZERO;
if (n == 0)
return this;
if (n < 0)
return shiftRight(-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 j = 0;
while (j < magLen - 1)
newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
newMag[i] = mag[j] << nBits;
}
return new BinaryInteger(newMag, signum);
}
/**
* 右移运算
*
* @param n
* shift distance, in bits.
* @return <tt>this >> n</tt>
* @see #shiftLeft
*/
public BinaryInteger shiftRight(int n) {
if (n == 0)
return this;
if (n < 0)
return shiftLeft(-n);
int nInts = n >>> 5;
int nBits = n & 0x1f;
int magLen = mag.length;
int newMag[] = null;
// Special case: entire contents shifted off the end
if (nInts >= magLen)
return (signum >= 0 ? ZERO : negConst[1]);
if (nBits == 0) {
int newMagLen = magLen - nInts;
newMag = new int[newMagLen];
for (int i = 0; i < newMagLen; i++)
newMag[i] = mag[i];
} else {
int i = 0;
int highBits = mag[0] >>> nBits;
if (highBits != 0) {
newMag = new int[magLen - nInts];
newMag[i++] = highBits;
} else {
newMag = new int[magLen - nInts - 1];
}
int nBits2 = 32 - nBits;
int j = 0;
while (j < magLen - nInts - 1)
newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
}
if (signum < 0) {
// Find out whether any one-bits were shifted off the end.
boolean onesLost = false;
for (int i = magLen - 1, j = magLen - nInts; i >= j && !onesLost; i--)
onesLost = (mag[i] != 0);
if (!onesLost && nBits != 0)
onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);
if (onesLost)
newMag = javaIncrement(newMag);
}
return new BinaryInteger(newMag, signum);
}
int[] javaIncrement(int[] val) {
boolean done = false;
int lastSum = 0;
for (int i = val.length - 1; i >= 0 && lastSum == 0; i--)
lastSum = (val[i] += 1);
if (lastSum == 0) {
val = new int[val.length + 1];
val[0] = 1;
}
return val;
}
// Bitwise Operations
/**
* Returns a BinaryInteger whose value is <tt>(this & val)</tt>.
* (This method returns a negative BinaryInteger if and only if this and val
* are both negative.)
*
* @param val
* value to be AND'ed with this BinaryInteger.
* @return <tt>this & val</tt>
*/
public BinaryInteger and(BinaryInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
for (int i = 0; i < result.length; i++)
result[i] = (int) (getInt(result.length - i - 1) & val
.getInt(result.length - i - 1));
return valueOf(result);
}
/**
* 位或运算
*
* @param val
* value to be OR'ed with this BinaryInteger.
* @return <tt>this | val</tt>
*/
public BinaryInteger or(BinaryInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
for (int i = 0; i < result.length; i++)
result[i] = (int) (getInt(result.length - i - 1) | val
.getInt(result.length - i - 1));
return valueOf(result);
}
/**
* 位异或运算
*
* @param val
* value to be XOR'ed with this BinaryInteger.
* @return <tt>this ^ val</tt>
*/
public BinaryInteger xor(BinaryInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
for (int i = 0; i < result.length; i++)
result[i] = (int) (getInt(result.length - i - 1) ^ val
.getInt(result.length - i - 1));
return valueOf(result);
}
/**
* 位取反操作
*
* @return <tt>~this</tt>
*/
public BinaryInteger not() {
int[] result = new int[intLength()];
for (int i = 0; i < result.length; i++)
result[i] = (int) ~getInt(result.length - i - 1);
return valueOf(result);
}
/**
* Returns a BinaryInteger whose value is <tt>(this & ~val)</tt>.
* This method, which is equivalent to <tt>and(val.not())</tt>, is
* provided as a convenience for masking operations. (This method returns a
* negative BinaryInteger if and only if <tt>this</tt> is negative and
* <tt>val</tt> is positive.)
*
* @param val
* value to be complemented and AND'ed with this BinaryInteger.
* @return <tt>this & ~val</tt>
*/
public BinaryInteger andNot(BinaryInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
for (int i = 0; i < result.length; i++)
result[i] = (int) (getInt(result.length - i - 1) & ~val
.getInt(result.length - i - 1));
return valueOf(result);
}
// Single Bit Operations
/**
* Returns <tt>true</tt> if and only if the designated bit is set.
* (Computes <tt>((this & (1<<n)) != 0)</tt>.)
*
* @param n
* index of bit to test.
* @return <tt>true</tt> if and only if the designated bit is set.
* @throws ArithmeticException
* <tt>n</tt> is negative.
*/
public boolean testBit(int n) {
if (n < 0)
throw new ArithmeticException("Negative bit address");
return (getInt(n / 32) & (1 << (n % 32))) != 0;
}
/**
* Returns a BinaryInteger whose value is equivalent to this BinaryInteger
* with the designated bit set. (Computes <tt>(this | (1<<n))</tt>.)
*
* @param n
* index of bit to set.
* @return <tt>this | (1<<n)</tt>
* @throws ArithmeticException
* <tt>n</tt> is negative.
*/
public BinaryInteger setBit(int n) {
if (n < 0)
throw new ArithmeticException("Negative bit address");
int intNum = n / 32;
int[] result = new int[Math.max(intLength(), intNum + 2)];
for (int i = 0; i < result.length; i++)
result[result.length - i - 1] = getInt(i);
result[result.length - intNum - 1] |= (1 << (n % 32));
return valueOf(result);
}
/**
* Returns a BinaryInteger whose value is equivalent to this BinaryInteger
* with the designated bit cleared. (Computes
* <tt>(this & ~(1<<n))</tt>.)
*
* @param n
* index of bit to clear.
* @return <tt>this & ~(1<<n)</tt>
* @throws ArithmeticException
* <tt>n</tt> is negative.
*/
public BinaryInteger clearBit(int n) {
if (n < 0)
throw new ArithmeticException("Negative bit address");
int intNum = n / 32;
int[] result = new int[Math.max(intLength(), (n + 1) / 32 + 1)];
for (int i = 0; i < result.length; i++)
result[result.length - i - 1] = getInt(i);
result[result.length - intNum - 1] &= ~(1 << (n % 32));
return valueOf(result);
}
/**
* Returns a BinaryInteger whose value is equivalent to this BinaryInteger
* with the designated bit flipped. (Computes <tt>(this ^ (1<<n))</tt>.)
*
* @param n
* index of bit to flip.
* @return <tt>this ^ (1<<n)</tt>
* @throws ArithmeticException
* <tt>n</tt> is negative.
*/
public BinaryInteger flipBit(int n) {
if (n < 0)
throw new ArithmeticException("Negative bit address");
int intNum = n / 32;
int[] result = new int[Math.max(intLength(), intNum + 2)];
for (int i = 0; i < result.length; i++)
result[result.length - i - 1] = getInt(i);
result[result.length - intNum - 1] ^= (1 << (n % 32));
return valueOf(result);
}
/**
* Returns the index of the rightmost (lowest-order) one bit in this
* BinaryInteger (the number of zero bits to the right of the rightmost one
* bit). Returns -1 if this BinaryInteger contains no one bits. (Computes
* <tt>(this==0? -1 : log<sub>2</sub>(this & -this))</tt>.)
*
* @return index of the rightmost one bit in this BinaryInteger.
*/
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 int
int i, b;
for (i = 0; (b = getInt(i)) == 0; i++)
;
lowestSetBit = (i << 5) + trailingZeroCnt(b);
}
}
return lowestSetBit;
}
// Miscellaneous Bit Operations
/**
* Returns the number of bits in the minimal two's-complement representation
* of this BinaryInteger, <i>excluding</i> a sign bit. For positive
* BigIntegers, this is equivalent to the number of bits in the ordinary
* binary representation. (Computes
* <tt>(ceil(log<sub>2</sub>(this < 0 ? -this : this+1)))</tt>.)
*
* @return number of bits in the minimal two's-complement representation of
* this BinaryInteger, <i>excluding</i> a sign bit.
*/
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 = ((mag.length - 1) << 5) + bitLen(mag[0]);
if (signum < 0) {
// Check if magnitude is a power of two
boolean pow2 = (bitCnt(mag[0]) == 1);
for (int i = 1; i < mag.length && pow2; i++)
pow2 = (mag[i] == 0);
bitLength = (pow2 ? magBitLength - 1 : magBitLength);
} else {
bitLength = magBitLength;
}
}
}
return bitLength;
}
/**
* bitLen(val) is the number of bits in val.
*/
static int bitLen(int w) {
// Binary search - decision tree (5 tests, rarely 6)
return (w < 1 << 15 ? (w < 1 << 7 ? (w < 1 << 3 ? (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32
: 0)
: 1)
: (w < 1 << 2 ? 2 : 3))
: (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6 : 7)))
: (w < 1 << 11 ? (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9)
: (w < 1 << 10 ? 10 : 11))
: (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13)
: (w < 1 << 14 ? 14 : 15))))
: (w < 1 << 23 ? (w < 1 << 19 ? (w < 1 << 17 ? (w < 1 << 16 ? 16
: 17)
: (w < 1 << 18 ? 18 : 19))
: (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21)
: (w < 1 << 22 ? 22 : 23)))
: (w < 1 << 27 ? (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25)
: (w < 1 << 26 ? 26 : 27))
: (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29)
: (w < 1 << 30 ? 30 : 31)))));
}
/*
* trailingZeroTable[i] is the number of trailing zero bits in the binary
* representation of i.
*/
final static byte trailingZeroTable[] = { -25, 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, ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -