Convert an array of bytes into one decimal number as a string

Question

I'm trying to write function that converts an arbitrary large array of bytes (larger than 64-bit) into a decimal number represented as string in c# and I simply can't figure out how to do it.

For example the following code ...

Console.WriteLine(ConvertToString(
  new byte[]
  { 
    0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 
    0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF, 0x00
  }));

.. should print out

22774453838368691933757882222884355840

I don't want to just use an extra library like biginteger for that, because I want it to be simple and like to understand how it works.

Answer 1

Some guidelines:

1. You will need to save the digits of the number in a matrix, one space for each digit. The matrix starts empty.
2. Then you need a matrix to save the multiplication of the matrix. It too starts empty.
3. Now for each byte you have:
   1. First multiply each digit of the current number matrix by 256, save the 10 modulus in the corresponding temporary digit and add the the number divided by 10 to the next digits multiplication.
   2. Assign the temporary multiplication matrix to the current digit matrix.
   3. Then add the byte to the first digit.
   4. Correct the current matrix, saving only the 10 modulus in each index and passing the value divided by 10 to the next index.
4. Then you need to concatenate each digit in a string.
5. Return the string.

Don't forget to expand each matrix as needed, or determine the maximum size needed from the number of bytes been passed.

Edit, example following the third step above:

Values = [0xAA, 0xBB] Initial Current = [] Initial Temp = []

With 0xAA

1. Nothing to multiply.
2. No change on assignment.
3. We add 0xAA to the first value in current: Current = [170]
4. We correct current to save only the modulus, passing the value divided by ten to the next value:
   1. 1st digit: Current = [0] pass 17.
   2. 2nd digit: Current = [0, 7] pass 1.
   3. 3rd digit: Current = [0, 7, 1] no value to pass so process ends.

Now with 0xBB

1. Multipli by 256, save in temp and correct, do for each digit:
   1. 1st digit: Temp = [0], 0 to save to the next digit.
   2. 2nd digit: Temp = [0, 1792] before correction, Temp = [0, 2], 179 to pass after correction.
   3. 3rd digit: Temp = [0, 2, 1 * 256 + 179 = 435] before correction, Temp = [0, 2, 5], 43 to pass after correction.
   4. 4th digit: Temp = [0, 2, 5, 43] before, Temp = [0, 2, 5, 3], 3 to pass after
   5. 5th digit: Temp = [0, 2, 5, 3, 4] before and after correction, no digit to save, so the multiplication ends.
2. Assing temp to current: Current = [0, 2, 5, 3, 4]; Temp = []
3. Add the current value to the first digit: Current = [187, 2, 5, 3, 4]
4. Correct the values:
   1. 1st digit: Current = [7, 2, 5, 3, 4], 18 to pass.
   2. 2nd digit: Current = [7, 0, 5, 3, 4], 2 to pass.
   3. 3rd digit: Current = [7, 0, 7, 3, 4], nothing to pass so the addition ends.

Now we only need to concatenate for the result 43707.

Answer 2

Based on @Wilheim's answer:

static string BytesToString(byte[] data) {
    // Minimum length 1.
    if (data.Length == 0) return "0";

    // length <= digits.Length.
    var digits = new byte[(data.Length * 0x00026882/* (int)(Math.Log(2, 10) * 0x80000) */ + 0xFFFF) >> 16];
    int length = 1;

    // For each byte:
    for (int j = 0; j != data.Length; ++j) {
        // digits = digits * 256 + data[j].
        int i, carry = data[j];
        for (i = 0; i < length || carry != 0; ++i) {
            int value = digits[i] * 256 + carry;
            carry = Math.DivRem(value, 10, out value);
            digits[i] = (byte)value;
        }
        // digits got longer.
        if (i > length) length = i;
    }

    // Return string.
    var result = new StringBuilder(length);
    while (0 != length) result.Append((char)('0' + digits[--length]));
    return result.ToString();
}

Answer 3

You want to understand the workings so take a look at super cool C# BigInteger Class @ CodeProject.

Also, I have stripped that class to bare essentials for this question. It can be optimized further. :)

Try copy and paste following code it works!!

using System;

public class BigInteger
{
    // maximum length of the BigInteger in uint (4 bytes)
    // change this to suit the required level of precision.

    private const int maxLength = 70;


    private uint[] data = null;             // stores bytes from the Big Integer
    public int dataLength;                 // number of actual chars used


    public BigInteger()
    {
        data = new uint[maxLength];
        dataLength = 1;
    }

    public BigInteger(long value)
    {
        data = new uint[maxLength];
        long tempVal = value;

        dataLength = 0;
        while (value != 0 && dataLength < maxLength)
        {
            data[dataLength] = (uint)(value & 0xFFFFFFFF);
            value >>= 32;
            dataLength++;
        }

        if (tempVal > 0)         // overflow check for +ve value
        {
            if (value != 0 || (data[maxLength - 1] & 0x80000000) != 0)
                throw (new ArithmeticException("Positive overflow in constructor."));
        }
        else if (tempVal < 0)    // underflow check for -ve value
        {
            if (value != -1 || (data[dataLength - 1] & 0x80000000) == 0)
                throw (new ArithmeticException("Negative underflow in constructor."));
        }

        if (dataLength == 0)
            dataLength = 1;
    }

    public BigInteger(ulong value)
    {
        data = new uint[maxLength];

        // copy bytes from ulong to BigInteger without any assumption of
        // the length of the ulong datatype

        dataLength = 0;
        while (value != 0 && dataLength < maxLength)
        {
            data[dataLength] = (uint)(value & 0xFFFFFFFF);
            value >>= 32;
            dataLength++;
        }

        if (value != 0 || (data[maxLength - 1] & 0x80000000) != 0)
            throw (new ArithmeticException("Positive overflow in constructor."));

        if (dataLength == 0)
            dataLength = 1;
    }

    public BigInteger(BigInteger bi)
    {
        data = new uint[maxLength];

        dataLength = bi.dataLength;

        for (int i = 0; i < dataLength; i++)
            data[i] = bi.data[i];
    }

    public BigInteger(byte[] inData)
    {
        dataLength = inData.Length >> 2;

        int leftOver = inData.Length & 0x3;
        if (leftOver != 0)         // length not multiples of 4
            dataLength++;


        if (dataLength > maxLength)
            throw (new ArithmeticException("Byte overflow in constructor."));

        data = new uint[maxLength];

        for (int i = inData.Length - 1, j = 0; i >= 3; i -= 4, j++)
        {
            data[j] = (uint)((inData[i - 3] << 24) + (inData[i - 2] << 16) +
                             (inData[i - 1] << 8) + inData[i]);
        }

        if (leftOver == 1)
            data[dataLength - 1] = (uint)inData[0];
        else if (leftOver == 2)
            data[dataLength - 1] = (uint)((inData[0] << 8) + inData[1]);
        else if (leftOver == 3)
            data[dataLength - 1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);


        while (dataLength > 1 && data[dataLength - 1] == 0)
            dataLength--;

        //Console.WriteLine("Len = " + dataLength);
    }

    public override string ToString()
    {
        return ToString(10);
    }

    public string ToString(int radix)
    {

        string charSet = "ABCDEF";
        string result = "";

        BigInteger a = this;

        BigInteger quotient = new BigInteger();
        BigInteger remainder = new BigInteger();
        BigInteger biRadix = new BigInteger(radix);

        if (a.dataLength == 1 && a.data[0] == 0)
            result = "0";
        else
        {
            while (a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0))
            {
                singleByteDivide(a, biRadix, quotient, remainder);

                if (remainder.data[0] < 10)
                    result = remainder.data[0] + result;
                else
                    result = charSet[(int)remainder.data[0] - 10] + result;

                a = quotient;
            }
        }

        return result;
    }

    private static void singleByteDivide(BigInteger bi1, BigInteger bi2,
                                         BigInteger outQuotient, BigInteger outRemainder)
    {
        uint[] result = new uint[maxLength];
        int resultPos = 0;

        // copy dividend to reminder
        for (int i = 0; i < maxLength; i++)
            outRemainder.data[i] = bi1.data[i];
        outRemainder.dataLength = bi1.dataLength;

        while (outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength - 1] == 0)
            outRemainder.dataLength--;

        ulong divisor = (ulong)bi2.data[0];
        int pos = outRemainder.dataLength - 1;
        ulong dividend = (ulong)outRemainder.data[pos];

        if (dividend >= divisor)
        {
            ulong quotient = dividend / divisor;
            result[resultPos++] = (uint)quotient;

            outRemainder.data[pos] = (uint)(dividend % divisor);
        }
        pos--;

        while (pos >= 0)
        {
            dividend = ((ulong)outRemainder.data[pos + 1] << 32) + (ulong)outRemainder.data[pos];
            ulong quotient = dividend / divisor;
            result[resultPos++] = (uint)quotient;

            outRemainder.data[pos + 1] = 0;
            outRemainder.data[pos--] = (uint)(dividend % divisor);
        }

        outQuotient.dataLength = resultPos;
        int j = 0;
        for (int i = outQuotient.dataLength - 1; i >= 0; i--, j++)
            outQuotient.data[j] = result[i];
        for (; j < maxLength; j++)
            outQuotient.data[j] = 0;

        while (outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength - 1] == 0)
            outQuotient.dataLength--;

        if (outQuotient.dataLength == 0)
            outQuotient.dataLength = 1;

        while (outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength - 1] == 0)
            outRemainder.dataLength--;
    }



    public static void Main(string[] args)
    {

        BigInteger big = new BigInteger(    new byte[]
                                  { 
                                    0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 
                                    0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF, 0x00
                                  });

        Console.WriteLine(big);

    }

}