Convert big hexadecimal to decimal numbers

Question

I have a big hexadecimal number, for example CD4A0619FB0907BC00000 (25!) or any other number like this. Now, using standard C/C++ code only (no libraries like Boost), I want to convert this number to the decimal number 15511210043330985984000000. Unfortunately, it's too big for a 64 bit integer (like long long) and I don't want to use any floating point data types either. If this is possible at all, how can you do this?

It is possible but you would be rewriting the code the libraries have already written. — NathanOliver, Jul 24 '15 at 15:11
@NathanOliver I don't actually want to rewrite the code, I just want to unterstand how it's done. — sigalor, Jul 24 '15 at 15:15
You need one or both of: converting from a base to an internal representation and/or converting to a base from an internal representation. If your internal representation is any kind of dense binary, then converting from hex to internal is trivial (doesn't require the general method). If your internal representation is decimal string, then converting from internal to decimal is unnecessary. General from a base conversion is simple left to right, multiply partial result then add next digit. General to a base is right to left divide and use the remainder as the output digit. — JSF, Jul 24 '15 at 15:20
floating-point types are not the solution for this as their precisions are limited — phuclv, Sep 06 '16 at 09:25

score 1 · Accepted Answer · answered Jul 24 '15 at 15:13

Assuming you don't want to use any of resources that might fit your description "libraries like Boost". The simple answer is to write your own subset of one, with just the operations you need. If 32 hex digits is enough, then simplest would be to create your own 128 bit unsigned int and code a divide by 10 function (producing quotient and remainder) for that 128-bit int. You really don't need any other functions and divide by 10 is pretty easy. Converting up to 32 hex digits to 128 bit int is trivial and generating decimal output from a series of divide by ten is trivial. If you want essentially unlimited size, then it is likely simpler to represent a decimal number as a string of digits and write a routine to multiply that by 16 and add in another digit. That would never be the efficient solution, just likely easier to code for your purpose and unlimited size.

Thanks, the static "division by 10"-function was the solution. I ended up with multiplying the number (internally represented by an array of bits) by 205 and performing a bitshift by 11 to the right, because 205/2048 is almost equal to 1/10. — sigalor, Jul 24 '15 at 15:39
I don't believe 205/2048 is a good enough approximation of 1/10 for your purpose. If you represent a binary number as a series of chunks smaller (not equal in size) than the max size for which you have a native divide, dividing by 10 is quite easy. Set an accumulator to zero, then for each chunk (from highest order to lowest order) shift the accumulator left by chunk size, add the chunk, seting that position of the quotient to the quotient and setting the accumulator to the remainder (of that native division). — JSF, Jul 24 '15 at 15:47

rcnjko · Answer 2 · 2016-09-06T09:18:40.810

vector<unsigned int> bin2dec(vector<unsigned int> binary)
{
    vector<unsigned int> decimal;
    bool all_zero = false;

    // binary[i]: stores 8-bit of the nubmer.
    // Ex. 258 = 0x102 => binary[0] = 0x2, binary[1] = 0x1.
    while (!all_zero) {
        all_zero = true;
        for (int i = binary.size() - 1; i >= 0; i--) {
            int q = binary[i] / 10;
            int r = binary[i] % 10;

            binary[i] = q;
            if (i > 0) {
                binary[i-1] += (r << 8);
            } else {
                decimal.insert(decimal.begin(), r);
            }
            if (q != 0) {
                all_zero = false;
            }
        }
    }
    // each element stands for one digit of the decimal number.
    // Ex. 258 => decimal[0] = 2, decimal[1] = 5, decimal[2] = 8.
    return decimal; 
}

score 0 · Answer 3 · edited May 23 '17 at 12:15

0

If you don't want to use external libraries then you will have to implement a arbitary-precision integer type yourself. See this question for ideas on how to do this. You will also need a function/constructor for converting hexadecimal strings to your new type. See this question for ideas on how to do this.

edited May 23 '17 at 12:15

Community

1
1

answered Jul 24 '15 at 15:14

Daniel

8,179
6
31
56

Convert big hexadecimal to decimal numbers

3 Answers3