I have a binary number, stored in an array of bytes (unsigned chars), and want to turn it into a decimal string.

The "obvious" approach that i found online was, to iterate over the array, add everything up while keeping track of the base and then converting it into a string but this doesn't work for me because the whole number doesn't fit into any common datatype and therefor cannot be added up in one go.

typedef unsigned char byte;

typedef struct Bin {
    int size;
    byte *ptrToVal;
} Bin;

void asDecString(Bin* this) {
    signed int n = 0;
    for(int i = 0; i < this->size; i  ) {
        n  = this->ptrToVal[i] << (i * 8);
        printf("%d\t%d\t%d\n", this->ptrToVal[i], n, i);
    }
    printf("%d\n", n);
}

The second, slow approach is to store the number in a string and multiply the digits in the string.

I'm looking for a quick way to implement this in c, but because I'm completely new to the language I don't know the features that well.

CodePudding user response：

For large integers; you want to break them into "small enough integers", then convert the "small enough integers" into digits.

For example, lets say you have the number 1234567890. By doing next_piece = number / 100; number = number % 100; you could split it into pieces that fit in one byte, then print the smaller pieces 12, 34, 56, 78, 90 (with nothing between them and leading zeros to ensure the piece 03 doesn't get printed as 3) so that it looks like a single larger number.

In the same way you could split it into pieces that fit in a 32-bit unsigned integer; so that each piece is from 0 to 1000000000, by doing something like next_piece = number / 1000000000; number = number % 1000000000;. For example, the number 11223344556677889900112233445566778899 could be split into 11, 223344556, 677889900, 112233445, 566778899 and then printed (with leading zeros, etc).

Of course for big integers you'd need to implement a "divide by 1000000000" that works with your data structure, that returns a uint32_t (the remainder or the next piece) and the original value divided by 1000000000.

This is where things get messy. Using an array of bytes is slow, and signed numbers are painful. To fix that you'd want something more like:

typedef struct AlternativeBin {
    int signFlag;
    int size;
    uint32_t *ptrToVal;
} AlternativeBin;

It wouldn't be hard to convert from your original format into this alternative format (if you can't just use this alternative format for everything).

The division loop would look something like (untested):

// WARNING: Destructive (the input value is used to return the quotient)

uint32_t getNextPiece(AlternativeBin * value) {
    uint64_t temp = 0;
    int i;

    // Do the division

    for(i = value->size - 1; i >= 0; i--) {
        temp = (temp << 32) | value->ptrToVal[i];
        value->ptrToVal[i] = temp / 1000000000ULL;
        temp = temp % 1000000000ULL
    }

    // Reduce the size of the array to improve performance next time

    while( (value->size > 0) && (value->ptrToVal[value->size - 1] == 0) ) {
        value->size--;
    }

    return temp;
}

..which means the "printing loop" (using recursion to reverse the order of pieces) might look like (untested):

// WARNING: Recursive and destructive (the input value is destroyed)

void printPieces(AlternativeBin * value) {
    uint32_t piece;

    piece = getNextPiece(value);
    if( !value_became_zero(value) ) {
        printPieces(value);
        printf("	" PRIu32, piece);   // Print it with leading zeros
    } else {
        printf("%" PRIu32, piece);     // No leading zeros on first piece printed
    }
}

The other minor inconvenience is that you'll want to print a '-' at the start if the value is negative (untested):

// WARNING: Destructive (the input value is destroyed)

void printValue(AlternativeBin * value) {
    if(value->signFlag) {
        printf("-");
    }
    printPieces(value);
}

If you wanted you could also create a copy of the original data here (get rid of the WARNING: Destructive comment by destroying a copy and leaving the original unmodified); and convert from your original structure (bytes) into the alternative structure (with uint32_t).

Note that it would be possible to do all of this with bytes (something like your original structure) using a divisor of 100 (instead of 1000000000). It'd just be a lot slower because the expensive getNextPiece() function will need to be called about 4.5 as many times.