m进制转换为n进制-任意进制转换算法

    这种题也是一道经典的面试题，主要考察进制转换细想，Coding质量等。

    当我们把十进制转成二进制的时候，我们通过辗转相除，取余，逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

    如下是C的详细的实现方法

void m2n(int m, char* mNum, int n, char* nNum) 
{
	int i = 0;
	char c, *p = nNum;

	//这是一个考察地方，是否能用最少乘法次数。
	while (*mNum != \'\\0\')
		i = i*m + *mNum++ - \'0\';
	
	//辗转取余
	while (i) {
		*p++ = i % n + \'0\';
		i /= n;
	}
	*p-- = \'\\0\';

	//逆置余数序列
	while (p > nNum) {
		c = *p;
		*p-- = *nNum;
		*nNum++ = c;
	}
}

    观察上面的代码，存在着众多的不足。例如，要对输入参数做检查，数值的大小收到int值最大值的限制等。不过好在一点，该算法的时间复杂度是O(n)的。

    但是我们霹雳无敌的赵大叔又提供了一种用Java实现的通用的进制转换方法，即使Windows的计算器也转不了的大数，这个算法也可以转。算和上面的算法相比，他的基本思想不变，还是辗转除，但是用了字符串做大数相除，很不错的创新点，赞一个。代码如下：

package test;

/**
 * 功能：将一个数从M进制转换成N进制
 * MValue：M进制数的字符串表示方法
 * Shang：保存中间运算结果
 * M：M进制
 * N：N进制
 */
public class M2N {
	// 在这里对输入赋值
	public static String MValue = "1231412423534674574757";
	public static String Shang = null;
	public static int M = 10;
	public static int N = 8;

	public static void main(String[] args) {
		String nValue = "";
		Shang = MValue;
		while(Shang.length() > 0) {
			nValue = qiuyu(Shang) + nValue;
		}
		System.out.println(nValue);
	}

	/**
	 * 功能：对给定的M进制字符串对n求余。
	 * 
	 * @param MTempValue
	 * @param m
	 * @param n
	 * @return
	 */
	public static String qiuyu(String MTempValue) {
		Shang = "";
		int temp = 0;
		while (MTempValue.length() > 0) {
			int t = getIntFromStr(MTempValue.substring(0, 1));
			MTempValue = MTempValue.substring(1);
			temp = temp * M + t;
			Shang += getStrFromInt(temp / N);
			temp = temp % N;
		}
		while(Shang.length() > 0 && Shang.charAt(0) == \'0\'){
			Shang = Shang.substring(1);
		}
		return getStrFromInt(temp);
	}

	public static int getIntFromStr(String str){
		return str.charAt(0) <= \'9\' && str.charAt(0) >= \'0\'? 
			str.charAt(0) - \'0\' : str.charAt(0) - \'a\' + 10;
	}

	public static String getStrFromInt(int value){
		String result = null;
		if (value >= 0 && value <= 9)
			result = String.valueOf((char)(\'0\' + value));
		else if (value > 9 && value < 36)
		{
			result = String.valueOf((char)(\'a\' + value - 10));
 		}
		else
		{
			result = "-1";// 出错误了
		}
		return result;
	}
}

    赵大叔的算法好了不少，除了参数检查，大小写之外都很好。值得我们借鉴。

    下载源码：

    M2N.Java (2.90 kb)