integer to string

Question

The strutils.h library contains a function IntegerToString. (You might have wondered how the computer actually goes about the process of converting an integer into its string representation.)

As it turns out, the easiest way to implement this function is to use the recursive decomposition of an integer.

Someone wrote a recursive implementation of IntegerToString so that it operates recursively without using any of the iterative constructs such as while and for.

Although it helped me ... i m not able to understand the code :S

#include <iostream>
#include <string>

using namespace std;

const char digit_pairs[201] = {
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899"
};


std::string& itostr(int n, std::string& s)
{
    if(n==0)
    {
        s="0";
        return s;
    }

    int sign = -(n<0);
    unsigned int val = (n^sign)-sign;

    int size;
    if(val>=10000)
    {
        if(val>=10000000)
        {
            if(val>=1000000000)
                size=10;
            else if(val>=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(val>=1000000)
                size=7;
            else if(val>=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(val>=100)
        {
            if(val>=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(val>=10)
                size=2;
            else
                size=1;
        }
    }
    size -= sign;
    s.resize(size);
    char* c = &s[0];
    if(sign)
        *c='-';

    c += size-1;
    while(val>=100)
    {
       int pos = val % 100;
       val /= 100;
       *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
       c-=2;
    }
    while(val>0)
    {
        *c--='0' + (val % 10);
        val /= 10;
    }
    return s;
}

just want to get better understanding of this code.

The code I linked to was for your understanding of how "real" implementation might look, as opposed to the "easy" recursive technique your teacher recommended. You aren't permitted to turn it my code as your own on the assignment (and even if you did, you're likely to be marked down for not using recursion as instructed) — Ben Voigt, Oct 28 '11 at 04:05
@Larry: You really messed with the question, and rewrote it to suggest that my code which user1002484 copied meets the constraints put on the assignment by his professor. It doesn't. The solution outlined in my answer would meet those requirements, but is designed as a hint to get things moving (as was originally requested). — Ben Voigt, Oct 28 '11 at 04:06

score 3 · Accepted Answer · edited May 23 '17 at 11:47

I think the "recursive decomposition" is

N = T * 10 + O

This leads to a recursive algorithm

string(N) = let T = idiv(N, 10),
            let O = mod(N, 10),
            concat(T? string(T): empty_string, todigit(O))

Now you just have to write that up in C++, figuring out the little details along the way.

Then if you want to see more efficient ways, read

C++ performance challenge: integer to std::string conversion

integer to string

1 Answers1