BigInteger简单分析

BigInteger简单分析

早上看到一篇写使用BigInteger计算阶乘的文章，看了下源码，有点小收获。

BigInteger的主要内部数据:

int signum; 

如果数值为正，则signum为1，值为负则signum为-1，值为0则signum为0。

int[] mag;

使用一个数组表示大数，例如: 如果大数用一个int就可以表示，则直接存这个数在mag[0]中，如果超出int的范围，就扩充这个数组，存储采用big endian方式。

简单分析，把BigInteger中的stripLeadingZeroBytes()函数拷贝出来并调用：

public class A {
	// Copy from the jdk 1.6 source code
	private static int[] stripLeadingZeroBytes(byte a[]) {
		int byteLength = a.length;
		int keep;

		// Find first nonzero byte
		for (keep = 0; keep < a.length && a[keep] == 0; keep++)
			;

		// Allocate new array and copy relevant part of input array
		int intLength = ((byteLength - keep) + 3) / 4;
		int[] result = new int[intLength];
		int b = byteLength - 1;
		for (int i = intLength - 1; i >= 0; i--) {
			result[i] = a[b--] & 0xff;
			int bytesRemaining = b - keep + 1;
			int bytesToTransfer = Math.min(3, bytesRemaining);
			for (int j = 8; j <= 8 * bytesToTransfer; j += 8)
				result[i] |= ((a[b--] & 0xff) << j);
		}
		return result;
	}

	public static void main(String[] args) {
		byte x[] = new byte[5];
		for (int i = 0; i < x.length; i++)
			x[i] = 2;
		System.out.println(Arrays.toString(stripLeadingZeroBytes(x)));
		System.out.println(new BigInteger(x).toString(2));
	}
}
output
=============
[2, 33686018]
1000000010000000100000001000000010    
// 分开就是 10  00000010  00000010  00000010  00000010

可以看出，此时的mag长度是2，mag[0] 保存的是溢出位2(big endian)。

顺便说一句，BigInteger和BigDecimal的作者是Bloch，都实现成他比较推崇的Immutable Object的形式，缺点是某些环境下可能产生性能问题。

=================================================
new updated 2010.1.4

可能产生性能问题时的解决方案
Bloch在Effect Java中对不可变类由于生产对象过多而可能产生性能问题提出了两种解决方案。

方案一：在不可变类中对可能产生重复数据的情况提供方法实现
例如：考虑到可能使用BigInteger进行幂元素，在BigInteger中直接提供pow函数:

BigInteger中的pow的内部实现并不会产生多余的BigInteger对象。但如果是个人使用BigInteger来实现x的n次方，即使使用平方后再相乘的方法，也会产生log2(N)个BigInteger对象，当n很大时，过多不必要的对象将占有大量空间，如果来不及回收则会导致out of memory。

提供这种方法实现的很大一个好处就是域共用，即：新产生的BigInteger可以共用“旧”的BigInteger的部分域。典型的例子有：

// BigInteger的negate()方法:
public BigInteger negate() {...}
// 新产生的BigInteger和旧的BigInteger仅仅符号位不同，mag数组时共用的。

// BigInteger的setBit()方法:
public BigInteger setBit(int n)
// 用于置BigInteger的某一位为1，新产生的BigInteger和旧的BigInteger仅仅在某个mag项不同。

缺点：不可能在不可变对象中提供所有可能的方法。

方案二：为不可变类提供一个相应的可变类
例如String是不可变类，StringBuilder是String的可变类。