Converting a number to a string and back

Question

I have always used streams, printf, string(x) or whatever the language in question offered to convert numeric types to a string or back. However I have never really considered how this is actually done. I searched around on Google, but all the results are just to use those varies methods, and not how the conversion is really done behind the scenes :(

For integers using binary, octal and hexadecimal seems fairly straight forward since each "digit" in the string represents a set group of bits (eg for the 2 hex digits I know its xxxxyyyy), so I could do it with bit shifts and taking one digit at a time, eg for the hex string 0xFA20 the value is "(15 << 12) | (10 << 8) | (2 << 4) | (0 << 0)".

Decimal integers are more difficult since base 10 doesn't map to base 2 like that and so one bit may effect more than one decimal digit making conversion both ways more complex...

As for floating point numbers I really have no idea. I guess the whole and fractional parts could be considered separately or something? What about as an exponential, a set number of significant figures or set number of decimal places?

Answer 1

I searched around on Google, but all the results are just to use those varies methods, and not how the conversion is really done behind the scenes :(

For performance reasons, converting from one representation to another (particularly floating-point/integer conversions) is often a low-level CPU instruction and is implemented at the processor level. That's why you don't typically see it re-implemented in libraries or at a language level.

This is especially common in the signal-processing world, for example, where you want to take a waveform and convert it into a discrete integer value in some range.

Answer 2

For integers you can find division remainder, this is last digit, divide by 10, found modular residual - this is one but last digit, and so on. Floating point numbers are constructed of two parts - significant digits and exponent, i.e. number = significant.digits * (base ^ exponent), where base can be 10, 2, or other number.

Answer 3

Decimal conversions are a bit slower, but not really a lot more complex. Let's look at the hexadecimal conversion a bit more like we'd probably write it in real code. Just for example, in C++ you might do the conversion something like this:

char digits[] = "0123456789abcdef";
std::string result;

int input = 0xFA20;

while (input) {
    int digit = input & 0xf; // or: digit = input % 0xf;
    input >>= 4;             // or: input /= 16;
    result.push_front(digits[digit]);
}

Right now, however, that has some magic numbers. Let's get rid of them:

const int base = 16;

while (input) { 
    int digit = input % (base - 1);
    input /= base;
    result.push_front(digits[digit]);
}

In the process of getting rid of those magic numbers, we've also made the routine nearly universal -- if we change the value of 'base', the rest of the routine still works, and converts the input to the specified base. Essentially the only other change we need to make is adding more to the "digits" array if we want to support bases larger than 16.

This also ignores a few things for simplicity. Most obviously, if the number is negative, you typically set a flag, convert to a positive number, and at the end if the flag was set, put a '-' into the string). With 2's complement there's a corner case for the maximally negative number, which can't be converted to a positive number (without converting to a type with more range). Typically you deal with that by promoting most types. For your largest integer type (which you can't promote) it's usually easiest to just hard-code that one value.

In principle floating point isn't a whole lot different -- you still basically do mathematical manipulations to generate one digit at a time. In fact, it gets more complex simply because you typically have to deal with a couple of different formats (at least a "basic" floating point and some sort of "Scientific" format), as well as variables for field width and precision. By the time you've dealt with that, you end up with a few hundred lines of code or so -- not a particularly outrageous amount, but probably a bit more than makes sense to include here.