非常长的正整数的基数转换

引言

使用 C# 中的内置模运算，在不同的进制之间转换长度高达 64 位 (UInt64) 的数字相对简单。

我需要转换具有数千位数字的数字，并且我编写了 BaseConverter 类来执行此操作。

此代码需要进一步的全面测试，但在我需要的所有情况下（其中输入足够短，可以通过其他方式验证）都似乎可以工作。毕竟，你如何验证数千位数字的正确结果？ 在实践中，我从较短的结果到较长的结果逐步进行测试用例，并对照已知的正确结果进行检查。 你也可以通过从输出基数返回到原始基数来进行反向转换来测试它，但这只能确认算法是对称的，而不是正确的。 也可以使用已知结果直接检查简单大数的有限情况。

用法

String out_num=BaseConverter.Convert(Int32 frombase,Int32 tobase,String in_num);

该算法可以转换正整数，潜在地可以在 2 到 36 范围内的任何进制之间转换数千位数字，包括但不限于二进制、八进制、十进制、十六进制。

该算法是在 Visual Studio 2005 C# 类中实现的，它具有一个 static 成员函数。 将 base16（十六进制）数字转换为 base 2（二进制）的示例调用是

String sout=BaseConverter.Convert(16,2,"14AFE");

答案是“10100101011111110”。

另一个将 base 19 转换为 base 7 的示例是

String sout=BaseConverter.Convert(19,7,"1IAHEB54638829348494387383AD12");

答案是“136615251021020315364261540624105412221316016”。

输入和输出

因为数字可以是任意位数的，所以我用 String 格式表示输入和输出数字。 每个数字都在 (0-Z) 范围内，但当然每个数字的最大值必须小于输入数字的基数。 所以 base 16（十六进制）由数字 (0-F) 表示，base 10 由 (0-9) 表示，base 2 由 (0-1) 表示，base 36 由 (0-Z) 表示。

最后，你当然必须指定输入数字的基数，以及输出数字所需的基数，以便算法知道要应用什么转换！

算法

输入数字从 string 转换为整数数组，每个数组元素代表输入数字的一位。 然后将以下过程应用于输入数字的每一位

首先计算每个数字的幂（从 frombase 到 i 次幂，其中 i=i^th 数字），并将其转换为输出基数中的整数数组表示形式。 通过从最低有效位到最高有效位累积结果来提高计算效率。 (p[n]=p[n-1]*frombase)。 此乘法中结转到下一个更高数字位置的任何数字都以递归方式添加，直到所有数字都由 tobase 数字表示形式表示。

然后将输入的每一位乘以该数字位置的幂并累积到结果中。 乘法中的任何进位数字再次递归地扩展到更高阶数字中，直到所有数字在输出基数格式中有效。

一旦输入字符串中的所有数字都已处理，输出结果将从整数数组转换回字符串格式。

代码

执行此转换的代码片段如下所示

//Copyright Andrew Jonkers 2006-
//convert a positive integer in base:from  to another base (allowable bases from 2 to 36)
//the number can be any number of digits long
//input and output in string format 
//(e.g. digits in base 2="0-1", base 16="0-F", base 20="0-J" etc
class BaseConverter
{
    //Convert number in string representation from base:from to base:to. 
    //Return result as a string
    public static String Convert(int from, int to, String s)
    {
        //Return error if input is empty
        if (String.IsNullOrEmpty(s))
        {
            return ("Error: Nothing in Input String");
        }
        //only allow uppercase input characters in string
        s = s.ToUpper();
        
        //only do base 2 to base 36 (digit represented by characters 0-Z)"
        if (from < 2 || from > 36 || to < 2 || to > 36) 
		{ return ("Base requested outside range"); }
        
        //convert string to an array of integer digits representing number in base:from
        int il = s.Length;
        int[] fs = new int[il];
        int k = 0;
        for (int i = s.Length - 1; i >= 0; i--)
        {
            if (s[i] >= '0' && s[i] <= '9') { fs[k++] = (int)(s[i] - '0'); }
            else
            {
                if (s[i] >= 'A' && s[i] <= 'Z') { fs[k++] = 10 + (int)(s[i] - 'A'); }
                else
                { return ("Error: Input string must only contain any of 
			0-9 or A-Z"); } //only allow 0-9 A-Z characters
            }
        }
        
        //check the input for digits that exceed the allowable for base:from
        foreach(int i in fs)
        {
            if (i >= from) { return ("Error: Not a valid number for this input base"); }
        }
        
        //find how many digits the output needs
        int ol = il * (from / to+1);
        int[] ts = new int[ol+10]; //assign accumulation array
        int[] cums = new int[ol+10]; //assign the result array
        ts[0] = 1; //initialize array with number 1 
        
        //evaluate the output
        for (int i = 0; i < il; i++) //for each input digit
        {
            for (int j = 0; j < ol; j++) //add the input digit 
				// times (base:to from^i) to the output cumulator
            {
                cums[j] += ts[j] * fs[i];
                int temp = cums[j];
                int rem = 0;
                int ip = j;
                do // fix up any remainders in base:to
                {
                    rem = temp / to;
                    cums[ip] = temp-rem*to; ip++;
                    cums[ip] += rem;
                    temp = cums[ip];
                }
                while (temp >=to);
            }
            
            //calculate the next power from^i) in base:to format
            for (int j = 0; j < ol; j++)
            {
                ts[j] = ts[j] * from;
            } 
            for(int j=0;j<ol;j++) //check for any remainders
            {
                int temp = ts[j];
                int rem = 0;
                int ip = j;
                do  //fix up any remainders
                {
                    rem = temp / to;
                    ts[ip] = temp - rem * to; ip++;
                    ts[ip] += rem;
                    temp = ts[ip];
                }
                while (temp >= to);
            }
        }
        
        //convert the output to string format (digits 0,to-1 converted to 0-Z characters) 
        String sout = String.Empty; //initialize output string
        bool first = false; //leading zero flag
        for (int i = ol ; i >= 0; i--)
        {
            if (cums[i] != 0) { first = true; }
            if (!first) { continue; }
            if (cums[i] < 10) { sout += (char)(cums[i] + '0'); }
            else { sout += (char)(cums[i] + 'A'-10); }
        }
        if (String.IsNullOrEmpty(sout)) { return "0"; } //input was zero, return 0
        //return the converted string
        return sout;
    }

历史

• 2006 年 10 月 18 日：初始帖子