Pnuts CC's Blog Flower & World, Life & Paradise.

Integer的toString()的效率优化（java）

偶然看了一下java中Integer和toString的方法实现，结果发现比自己想象中的要复杂的多，其中运用了各种提高效率的手段，于是学习了一番，在此保做个记录。以下是java的Integer的toString()的实现方法。

public static String toString(int i) {
	if (i == Integer.MIN_VALUE)
		return "-2147483648";
	int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
	char[] buf = new char[size];
	getChars(i, size, buf);
	return new String(0, size, buf);
}

这个方法没有太多实质性的内容，也很容易看懂，其中stringSize()是用于求出转化后的string的长度的。为了提高效率，这个方法采用查表，实现如下：

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
	99999999, 999999999, Integer.MAX_VALUE };

// Requires positive x
static int stringSize(int x) {
	for (int i=0; ; i++)
		if (x <= sizeTable[i])
			return i+1;
}

算法的核心在getChars方法中，从getChars的方法注释中可以看到，当i == Integer.MIN_VALUE 时，getChars方法会失效。这就是为什么toString(int i)的第一句要判断输入是否为整数的下界。（失效的原因在于getChars方法中会将负数转化为正数，而 Integer.MAX_VALUE = ( - Integer.MIN_VALUE ) - 1 ，所以当输入为Integer.MIN_VALUE时，化为正数的时候会溢出。）

getChars的方法体如下：

static void getChars(int i, int index, char[] buf) {
	int q, r;
	int charPos = index;
	char sign = 0;

	if (i < 0) {
		sign = '-';
		i = -i;
	}

	// Generate two digits per iteration
	while (i >= 65536) {
		q = i / 100;
		// really: r = i - (q * 100);
		r = i - ((q << 6) + (q << 5) + (q << 2));
		i = q;
		buf [--charPos] = DigitOnes[r];
		buf [--charPos] = DigitTens[r];
	}

	// Fall thru to fast mode for smaller numbers
	// assert(i <= 65536, i);
	for (;;) {
		q = (i * 52429) >>> (16+3);
		r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
		buf [--charPos] = digits [r];
		i = q;
		if (i == 0) break;
	}
	if (sign != 0) {
		buf [--charPos] = sign;
	}
} 

final static char [] DigitTens = {
	'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
	'1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
	'2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
	'3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
	'4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
	'5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
	'6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
	'7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
	'8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
	'9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
	} ; 

final static char [] DigitOnes = {
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	} ;

final static char[] digits = {
	'0' , '1' , '2' , '3' , '4' , '5' ,
	'6' , '7' , '8' , '9' , 'a' , 'b' ,
	'c' , 'd' , 'e' , 'f' , 'g' , 'h' ,
	'i' , 'j' , 'k' , 'l' , 'm' , 'n' ,
	'o' , 'p' , 'q' , 'r' , 's' , 't' ,
	'u' , 'v' , 'w' , 'x' , 'y' , 'z'
};

可以看到，方法会根据输入的数的数量级来采用不同的处理方法。

当i >=65536时，以100为单位，通过i - ( i / 100 * 100 )的方式来获得最后两位，然后分别查DigitTens和DigitOnes两个表，直接获取十位和个位。

其中的(q >> 6) + (q >> 5) + (q >> 2)实际就是在计算q * 100，2 ^ 6 + 2 ^ 3 + 2 ^ 2 = 100。只不过移位的耗时更少而已。

当i < 65536时，通过i - ( i / 10 * 10 )来获得每一位。

这里的 q = (i * 52429) >>> (16+3)可能会让人费解，实际2 ^ 19 = 524288，而52429 / 524288 = 0.10000038146972656，约为0.1，所以这一步实际就是在除以10，只不过是换种效率更高的方法而已。

值得一提的是除了52429外，还有很多数可以选，如：

2^10=1024, 103/1024=0.1005859375

2^11=2048, 205/2048=0.10009765625

2^12=4096, 410/4096=0.10009765625

2^13=8192, 820/8192=0.10009765625

2^14=16384, 1639/16384=0.10003662109375

2^15=32768, 3277/32768=0.100006103515625

2^16=65536, 6554/65536=0.100006103515625

2^17=131072, 13108/131072=0.100006103515625

2^18=262144, 26215/262144=0.10000228881835938

2^19=524288, 52429/524288=0.10000038146972656

当然，选52429也不是偶然，而是因为它是是在不超出整形范围内，精度最高的一个。

到此，方法就分析完了，不得不说啊，强人对效率的优化还是让人瞠目结舌的，似乎可以以cpu的时钟周期来计量了。学习了～

转载注明出处：http://pnuts.cc/2010/01/int-to-string/

P.S.

1. 六维元旦免积分下载，结果忽然发现自己没有想下的东西。

2. 每次碰工作室的门把手都会被电到，悲剧。

3. 想学日语了，原因不明。