Binary to Decimal... just harder!

[Labdabeta]

I have a problem that I am having trouble solving. I have a string of undefined length containing '0' or '1'. I need to convert this string to decimal... but I CANNOT store it in anything but another string. My issue is how to do this?! I have been thinking of maybe using base 1024, convert it to base 1000 + base 24 and store the 24 in an unsigned long long int... but even that might not work. Any ideas?

[Arbus]

Hello Labdabeta,
I hope you are asking to convert the string into integer(binary number) and then converting it to decimal. If yes,try this one..
For example, if there is '1' in a[0] then subtracting a[0] and '0' will give 1.

int b;
char a[100];
b=a[0]-'0';

The ASCII value of '1'(which is 49) is subtracted with ASCII value of '0'(which is 48).
Do this in a loop. Then you will have the binary number. Convert it into decimal.

[Moschops]

Do you mean the output has to be a string, or do you mean that you're forbidden from using anything but a string in your code?

[Labdabeta]

Basically I need to convert a binary number in the form of a string into the same number in decimal format in the form of a string. The numbers have to be able to handle upwards of 100 bytes, so storing them to ints just will not do.

[mike_2000_17]

First of all, assuming your binary string is stored from most significant bit to least significant bit, you will have to traverse it in reverse (from the end to the start), which isn't a big deal.

The same goes for the output string. You will have to preallocate enough storage for the output string (e.g. the size of the input string, or one third of that, since 3 bits represent at most 7 in decimal, but 4 bits go beyond one digit in the decimal base (i.e. 15)). Then, you can set its characters starting from the last (least-significant digit), at the end, you can copy the string back to the start if you used fewer digits than the preallocated amount.

As for computing the actual digits, that just requires a bit of arithmetic. Your main problem is going to be that all bits will yield a decimal representation with no trailing zeros. This means, you will always have to go all the way back to the least-significant digit of your output string and update its value based on the current bit you have that is not 0 (i.e. 1). In order to avoid overflowing integers, you will have to make wise use of modulus and bitshifting. When you figure out what value a particular bit contributes to a particular digit, then it is just a matter of doing addition with a carry (like you did in elementary school). This certainly isn't a trivial problem, but just try to do it by hand (pen and paper) and try to see what systematic procedure you (as an intelligent person, and not a stupid computer) could do to work this out.

[mike_2000_17]

Another thing that might help, notice that the least-significant digit of successive powers of 2, starting from 2, follow a fixed sequence: 2,4,8,6,2,4,8,6,2,4,8,6,... I'm sure there a sequences like that for other digits too!

You could also map all the triplets of bits to an octal representation (base 8, which is easy because it maps directly from 3 bits) and work from that intermediate representation to construct the decimal representation. Octal arithmetic might be less tedious than binary arithmetic.

Probably, the easiest solution is to convert first to BCD (Binary-Coded Decimal) which restricts every 4 bit sequence to be less than 10 and then the conversion to decimal is trivial. Here is a simple algorithm to convert a binary sequence to a BCD sequence.

[nezachem]

> First of all, assuming your binary string is stored from most significant bit to least significant bit, you will have to traverse it in reverse

No no no. Direct traversal is much simpler. Two methods need to be implemented: double a decimal string and add a bit value (0 or 1) to a decimal string.

In a pseudocode,

initialize a resulting decimal string
for each "bit"
    double_decimal_string
    add bit value to a decimal string

double_decimal_string
    set carry to 0
    for each digit in a string
        double digit
        add carry
        if result > 10
            subtract 10
            set carry to 1
        else
            set carry to 0

> I'm sure there a sequences like that for other digits too!
I seriously doubt that.