What's an Efficient Inversion of the Convert-to-Arbitrary-Base C# Function?

Question

I need to convert an integer into a base64-character representation. I'm using OxA3's answer on this thread: http://stackoverflow.com/questions/923771/quickest-way-to-convert-a-base-10-number-to-any-base-in-net

How do I inverse this to get my original integer back, given a string?

Answer 1

I have a first-pass of a working version here, albeit I'm not sure how efficient it is.

public static int StringToInt(string encodedString)
    {
        int result = 0;
        int sourceBase = baseChars.Length;
        int nextCharIndex = 0;

        for (int currentChar = encodedString.Length - 1; currentChar >= 0; currentChar--)
        {
            char next = encodedString[currentChar];

            // For loop gets us: baseChar.IndexOf(char) => int
            for (nextCharIndex = 0; nextCharIndex < baseChars.Length; nextCharIndex++)
            {
                if (baseChars[nextCharIndex] == next)
                {
                    break;
                }
            }

            // For character N (from the end of the string), we multiply our value
            // by 64^N. eg. if we have "CE" in hex, F = 16 * 13.
            result += (int)Math.Pow(baseChars.Length, encodedString.Length - 1 - currentChar) * nextCharIndex;
        }

        return result;
    }

Answer 2

If base-64 is really what you need rather than "any base" then everything you need is already built in to the framework:

int orig = 1337;
byte[] origBytes = BitConverter.GetBytes(orig);
string encoded = Convert.ToBase64String(origBytes);
byte[] decoded = Convert.FromBase64String(encoded);
int converted = BitConverter.ToInt32(decoded, 0);
System.Diagnostics.Debug.Assert(orig == converted);

Answer 3

Joel Mueller's answer should guide you the base-64 case.

In response to the preliminary code you've provided in your own answer, you can definitely improve its efficiency by changing the code to accomplish what your for loop is doing (effectively an O(N) IndexOf) to use a hash lookup (which should make it O(1)).

I am basing this on the assumption that baseChars is a field that you initialize in your class's constructor. If this is correct, make the following adjustment:

private Dictionary<char, int> baseChars;

// I don't know what your class is called.
public MultipleBaseNumberFormatter(IEnumerable<char> baseCharacters)
{
    // check for baseCharacters != null and Count > 0

    baseChars = baseCharacters
        .Select((c, i) => new { Value = c, Index = i })
        .ToDictionary(x => x.Value, x => x.Index);
}

Then in your StringToInt method:

char next = encodedString[currentChar];

// No enumerating -- we've gone from O(N) to O(1)!
if (!characterIndices.TryGetValue(next, out nextCharIndex))
{
    throw new ArgumentException("Input includes illegal characters.");
}