My own itoa()

I tried to make my own itoa() function. I did it just for fun:

Code:

---

char* myitoa(int number,char* buffer,int radix){
        int increment=1,n,num;
        char temp[32];
        radix%=37;
        for(n=0;number>0;n++){
                increment*=radix;
                num=(number%increment)/(increment/radix);
                temp[n]=num+0x30;
                if(num>9){
                        temp[n]+=7;
                }
                number-=num*(increment/radix);
        }
        for(int i=0;i<n;i++){
                buffer[n-1-i]=temp[i];
        }
        buffer[n]='\0';
        return buffer;
}

---

Am I doing anything wrong here? Do you have any suggestions what I could do better when developing such functions?

>Am I doing anything wrong here?
You don't handle 0 or negative values. That's even worse than the usual issue where people fail to account for INT_MIN on a two's complement machine. ;)

Quote:

---

You don't handle 0 or negative values. That's even worse than the usual issue where people fail to account for INT_MIN on a two's complement machine.

---

That's so easy to fix.

But there is one really dangerous bug in my code, when you want to convert an integer that has maximum places it may have (1000000000-2147483647), the increment variable wants to jump into 10000000000, but it can't because it reached the limit 2147483647.

>That's so easy to fix.
It's only okay to be arrogant when your code does what it claims to do. Besides, if it's so easy to fix, why didn't you do it right in the first place? :rolleyes:

Quote:

---

Originally Posted by Prelude

>That's so easy to fix.
It's only okay to be arrogant when your code does what it claims to do. Besides, if it's so easy to fix, why didn't you do it right in the first place? :rolleyes:

---

I didn't think of negative numbers in the first place...

>I didn't think of negative numbers in the first place...
Then that answers your second question. To do better in developing such functions, you consider all possible input values and handle them accordingly. :)

Code:

---

char* myitoa(int number,char* buffer,int radix){
        int increment=1,n,num;
        bool negative=false;
        char temp[32];
        radix%=37;
        if(number==0){
                buffer[0]='0';
                buffer[1]='\0';
                return buffer;
        }
        if(number<0){
                negative=true;
                number*=-1;
        }
        for(n=0;number>0;n++){
                increment*=radix;
                num=(number%increment)/(increment/radix);
                temp[n]=num+0x30;
                if(num>9){
                        temp[n]+=7;
                }
                number-=num*(increment/radix);
        }
        if(negative){
                temp[n]='-';
                n++;
        }
        for(int i=0;i<n;i++){
                buffer[n-1-i]=temp[i];
        }
        buffer[n]='\0';
        return buffer;
}

---

I still don't know how to fix what I previously said. Any ideas?

Are you positive that buffer[] won't be NULL ever?

You mean that I should check it for NULL?

And what should I return then? NULL?

Yes and yes.

As for your big integer problem, you could check for integer overflow. Remember that when integers get too huge they wrap around to something small so if number + 1 < number, you have a problem. There's probably better ways to check for it though.

>You mean that I should check it for NULL?
You can if you want. Or you can just assume that it's not null, just as you have to assume that it's a pointer to memory that you can modify. I think most itoa implementations allocate a buffer and return it if the argument is null.

>I still don't know how to fix what I previously said. Any ideas?
You're seriously over-engineering this function. Let's walk through some design stages using some itoa reference material. First is the signature, and an incremental design means starting with a stub. Because itoa may exist in your implementation, a unique name is best:

Code:

---

char *jsw_itoa ( int value, char *buffer, int radix )
{

}

---

Then a good idea is to add comments to the stub that outline your tasks. First is to deal with critical errors that we have control over. With the reference given, I can see one that relates to a range check:

Quote:

---

Numeral radix in which value has to be represented, between 2 and 36.

---

The reference states that we can assume buffer points to writable memory large enough to hold the string representation of the value, but here's an interesting one:

Quote:

---

If radix is 10 and value is negative the string is preceded by the minus sign (-). With any other radix, value is always considered unsigned.

---

Negative values are only accepted if the radix is 10, otherwise the sign is ignored. This can be tricky if it doesn't fall out of your algorithm naturally, so that's a deciding factor in how to go about doing the conversion. Ideally, if you can keep it to a boolean flag then you're doing good. :) So let's look at the stub with task comments added for the ideal solution:

Code:

---

char *jsw_itoa ( int value, char *buffer, int radix )
{
    // Check the radix for an out of range error

    // Determine whether to handle the sign

    // Convert value to a string; ignore the sign

    // Handle the sign

    // Reverse the string
}

---

The last comment is where experience comes in. I know that the easiest way to break apart a numeric value is to iteratively chop off the least significant digit. But it's awkward to build a string from end to beginning, which would be required if the sequence of digits comes in from least significant to most significant. So the least awkward solution is to build the string backwards and the reverse it before returning.

With an idea of what you want to do, you can fill in the blanks for the easy stuff:

Code:

---

#include <algorithm>
#include <stdexcept>

namespace {
    const int min_radix = 2;
    const int max_radix = 36;
}

char *jsw_itoa ( int value, char *buffer, int radix )
{
    // Check the radix for an out of range error
    if ( radix < min_radix || max_radix < radix )
        throw std::range_error ( "Radix out of range" );

    // Determine whether to handle the sign
    bool sign = value < 0 && radix == 10;

    // Convert value to a string; ignore the sign

    // Handle the sign

    // Reverse the string
    std::reverse ( buffer, buffer + i );

    return buffer;
}

---

For notational convenience, the min and max for the radix should be given meaningful names. Magic numbers should be avoided wherever possible. The actual range check is straightforward. Since we're hoping that a boolean flag will be enough, the check for handling the sign is as simple as matching the description of when to deal with negative numbers: if value is negative and radix is 10. The string reversal is trivial thanks to the standard library, and on success the filled buffer is returned. So far so good, right? Now for the hard part.

If you were doing an itoa that just worked with decimal then the first thing that would come to mind is a quickie calculation:

Code:

---

do
    buffer[i++] = (char)( value % 10 ) + '0';
while ( ( value /= radix ) != 0 );

---

However, because you need to handle more than one radix, all the way through 36, it's probably better to use a table lookup. Consider it an extension of the itox-style conversion trick (which is another place where experience comes in):

Code:

---

#include <algorithm>
#include <cstdlib>
#include <stdexcept>

namespace {
    const int min_radix = 2;
    const int max_radix = 36;
    const char *digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
}

char *jsw_itoa ( int value, char *buffer, int radix )
{
    // Check the radix for an out of range error
    if ( radix < min_radix || max_radix < radix )
        throw std::range_error ( "Radix out of range" );

    // Determine whether to handle the sign
    bool sign = value < 0 && radix == 10;

    // Convert value to a string; ignore the sign
    int i = 0;

    do {
        int j = std::abs ( value % radix );
        buffer[i++] = digit[j];
    } while ( ( value /= radix ) != 0 );

    // Handle the sign

    buffer[i] = '\0';

    // Reverse the string
    std::reverse ( buffer, buffer + i );

    return buffer;
}

---

This is a fantastic solution. Remember how I said that handling negative values should just fall out of the algorithm naturally? This is an excellent example of that because if value is negative, we need to take the absolute value to ensure a safe index for the digit string. Conveniently enough, that also correctly handles INT_MIN for two's complement, so you don't have to think hard about that fix like you would with a calculation (even though the solution is the same). Also, since we've locked down how characters are added to the string, we can safely terminate it with '\'0' at the end.

That was the hard part. With all of the current framework in place, handling the sign is trivial. Since the algorithm completely ignores the sign aside from this point, if the boolean flag is not true then the algorithm effectively treats the value as unsigned, as per the requirements. With that done you have the final version, and it's far from complicated:

Code:

---

#include <algorithm>
#include <cstdlib>
#include <stdexcept>

namespace {
    const int min_radix = 2;
    const int max_radix = 36;
    const char *digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
}

char *jsw_itoa ( int value, char *buffer, int radix )
{
    // Check the radix for an out of range error
    if ( radix < min_radix || max_radix < radix )
        throw std::range_error ( "Radix out of range" );

    // Determine whether to handle the sign
    bool sign = value < 0 && radix == 10;

    // Convert value to a string; ignore the sign
    int i = 0;

    do {
        int j = std::abs ( value % radix );
        buffer[i++] = digit[j];
    } while ( ( value /= radix ) != 0 );

    // Handle the sign
    if ( sign )
        buffer[i++] = '-';

    buffer[i] = '\0';

    // Reverse the string
    std::reverse ( buffer, buffer + i );

    return buffer;
}

---

Designing a function like this is a combination of familiarity with similar solutions and a keen eye for detail. Reference material is important if the function already exists elsewhere, and a solid set of requirements if it's a completely new function. As long as you strictly adhere to the requirements, and the requirements are reasonable, you can usually pull an elegant solution out of them.

This code got quite long...

Code:

---

char* myitoa(int number,char* buffer,int radix){
    int n,num;
    bool negative=false;
    char temp[32];
    radix%=37;
    if(buffer==NULL){
        return NULL;
    }
    if(number<0){
        if(radix==10){ negative=true; }
        number*=-1;
    }
    for(n=0;number>0;n++){
        num=number%radix;
        temp[n]=num+0x30;
        if(num>9){
            temp[n]+=7;
        }
        number/=radix;
    }
    if(!n){ temp[n]='\0';n++; }
    if(negative){
        temp[n]='-';
        n++;
    }
    for(int i=0;i<n;i++){
        buffer[n-1-i]=temp[i];
    }
    buffer[n]='\0';
    return buffer;
}

---

The first code was quite stupid. It would've been much easier to multiply the number by radix every time.

I like to do my own functions, because it's interesting, I even need to think how to do it.
I am probably never going to use them.

What does itoa() do anyway?

Converts an integer to a string represented by an array of characters, or i to a. Basically the opposite of atoi.

>This code got quite long...
Have you tested it?

Code:

---

std::cout<< myitoa ( INT_MIN, buffer, 10 ) << '\n';
std::cout<< myitoa ( 0, buffer, 10 ) <<'\n';

---

Strange... it can't convert INT_MIN but it can convert INT_MIN+1... also it can convert INT_MAX.

Code:

---

char* myitoa(int number,char* buffer,int radix){
    int n,num;
    bool negative=false;
    char temp[32];
    radix%=37;
    if(buffer==NULL){
        return NULL;
    }
    if(number==0){
                buffer[0]='0';
                buffer[1]='\0';
                return buffer;
        }
    if(number<0){
        if(radix==10){ negative=true; }
        number*=-1;
    }
    for(n=0;number>0;n++){
        num=number%radix;
        temp[n]=num+0x30;
        if(num>9){
            temp[n]+=7;
        }
        number/=radix;
    }
    if(!n){ temp[n]='\0';n++; }
    if(negative){
        temp[n]='-';
        n++;
    }
    for(int i=0;i<n;i++){
        buffer[n-1-i]=temp[i];
    }
    buffer[n]='\0';
    return buffer;
}

---

This is precisely why I think C++0x should include rudimentary support for multiple precision arithmetic.

>Strange... it can't convert INT_MIN but it can convert INT_MIN+1... also it can convert INT_MAX.
Think about it for a moment. On your machine, INT_MAX is probably 2,147,483,647 and INT_MIN is -2,147,483,648. On a two's complement machine, the smallest negative number is one greater than the largest positive number. It's easy to just remove the sign and work with numbers from -2,147,483,647 to 2,147,483,647, but that last negative value won't play well because you can't represent it using a signed integer type.

One viable solution is to use an unsigned variable as a temporary. Since you assume unsigned except in one special case anyway, and that special case has no need to use the number in a signed sense, it's a quick and easy fix. Off the top of my head, your code could be changed like so:

Code:

---

char* myitoa(int number,char* buffer,int radix){
    unsigned x = number;
    int n,num;
    bool negative=false;
    char temp[32];
    radix%=37;
    if(buffer==NULL){
        return NULL;
    }
    if(number==0){
        buffer[0]='0';
        buffer[1]='\0';
        return buffer;
    }
    if(number<0){
        if(radix==10){
            negative=true;
            x = -number;
        }
    }
    for(n=0;x>0;n++){
        num=x%radix;
        temp[n]=num+0x30;
        if(num>9){
            temp[n]+=7;
        }
        x/=radix;
    }
    if(!n){ temp[n]='\0';n++; }
    if(negative){
        temp[n]='-';
        n++;
    }
    for(int i=0;i<n;i++){
        buffer[n-1-i]=temp[i];
    }
    buffer[n]='\0';
    return buffer;
}

---

You should assert() that buffer is not null, to catch such errors in debug builds while not losing performance in release builds.

In my opinion, you should also require that the buffer size be passed, and check that you're not overflowing. This is the idea behind MS's new s_* functions, and while I hate their execution, the idea is sound.
You might say that it's easy to pass a buffer that's long enough because the size of a converted integer is known at compile-time. But what if the radix is a runtime value? What if the program needs to be ported from, say, 16-bit ints to 32-bit ints? Will the buffer still be large enough?

The way negatives are handled, being ignored in any base but 10, I find counter-intuitive and seriously weird, especially as your function does not even output the real bit pattern in that case, but instead what the bit pattern would be if the parameter was not negative. I'd get rid of it and always handle them, simply by prepending a minus sign.

The internal temp buffer would be too small on systems with more than 32 bits in int. True, these are probably rare, but you never know. (Of course, on such platforms your ASCII-bound digit generation will probably fail, too.) Also, if you handle negatives consistently, it is too small now.
You should calculate its size like so:

Code:

---

#include <climits>
...
char temp[sizeof(int) * CHAR_BITS + 1];

---