Numeric Converter (big integers in string format)

Question

I'm trying to write a class in C# that converts a big number (string format) to any number system, I found this code at How to convert a gi-normous integer (in string format) to hex format? (C#)

    var s = "843370923007003347112437570992242323";
    var result = new List<byte>();
    result.Add( 0 );
    foreach ( char c in s )
    {
        int val = (int)( c - '0' );
        for ( int i = 0 ; i < result.Count ; i++ )
        {
            int digit = result[i] * 10 + val;
            result[i] = (byte)( digit & 0x0F );
            val = digit >> 4;
        }
        if ( val != 0 )
            result.Add( (byte)val );
    }

    var hex = "";
    foreach ( byte b in result )
        hex = "0123456789ABCDEF"[ b ] + hex;

This code also works for any numeric system (2^n base) with a few modifications to the code.

The problem is that I do not understand the logic of the algorithm (the for statement). Can someone please explain this part of the code:

for ( int i = 0 ; i < result.Count ; i++ )
{
    int digit = result[i] * 10 + val;
    result[i] = (byte)( digit & 0x0F );
    val = digit >> 4;
}
if ( val != 0 )
    result.Add( (byte)val );

In order to make this code to convert, for example, a string decimal to a string base64, I need to change the mask so it can calculate six bits, instead of just four for the hex system, and then right-shift digit by 6 to add the remaining to the next byte.

 result[i] = (byte)( digit & 0x03F );
 val = digit >> 6;  // 2^6 = 64

and finally just change the look-up table to print the result

hex =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" [ b ] + hex;

It is this line in the for-loop the one I don't totally understand

int digit = result[i] * 10 + val;

What is this line, along with the loop, doing on each iteration to every byte of result? and most importantly, why?

Sort of figuring it out. Let's say string was just '8'. Then digit = 8, result[i] = 8, val = 0, no added byte => 8 (1 byte). Next char is 4; digit is 84, result[0] is 5, val is 4 => 54 (2 bytes). — Jiminion, Aug 02 '13 at 01:25
Welcome to [so]. I upvoted, why downvotes people? and why the close as off-topic, its a question about `a software algorithm`? — Jeremy Thompson, Aug 02 '13 at 01:27
@JeremyThompson it is a copy/paste from the other question and does not show minimal understanding about the problem. — I4V, Aug 02 '13 at 01:39
Algorithm was not explained in original post. And he cited it. — Jiminion, Aug 02 '13 at 01:42
fair enough, OP could step through code to understand the bit-wise and bit-shift operations. — Jeremy Thompson, Aug 02 '13 at 01:42
I do understand the code, the bit-wise and bit-shift operators, in fact I modified the code so it can convert any integer (string decimal format) to any numeric system with base 2 to the n. Maybe i was not cleared with my question, but what I would like to know is the logic of the algorithm. So, yes @JeremyThompson, this is a software algorithm question. — hcaldera, Aug 02 '13 at 06:42

score 3 · Accepted Answer · answered Aug 02 '13 at 08:52

Perhaps the code is easier to understand if you compare the algorithm to the simpler version where the integer can be represented in an int. Then result would be a 32 bit integer which you would initialize to 0 and for each digit you would multiply the existing value of result with 10 and add the next digit:

int result = 0;
foreach ( char c in s ) {
  int val = (int)( c - '0' );
  result = 10*result + val;
}

For big integers you need a byte array to represent the integer and the loop that you want to understand is a way to multiply the value in the byte array of unknown length with 10 while also adding the digit value. Because multiplying by 10 is not a simple bit shift you need that extra code.

Numeric Converter (big integers in string format)

1 Answers1