Trying to write itoa

[AnujSuper9]

Hello everyone, I'm working on a small assignment where I am supposed to write the code for the itoa function

char* itoa(int Value, int Base);

without using any built-in functions, and where the returned value is allocated on behalf of the caller. Value being the integer to convert, and base being octal, decimal, or hex.

I found this rather simple implementation and I was hoping we could discuss it here to see if the changes I'm making are appropriate/accurate and etc.

char* itoa(int val, int base){
  static char buf[32] = {0};
  int i = 30;
  for(; val && i ; --i, val /= base)
    buf[i] = "0123456789abcdef"[val % base];
  return &buf[i+1];
}

Here's my current, pseudo-codey implementation:

char* itoa(int val, int base){

  static char buf[36] = {0};
  buf = (char *) malloc(//...);

  if (val == 0)
    return &buf=0;

  //since base can only be octal, decimal or hex
  if (base != 8 || base != 10 || base != 16)
    printf("Not a valid base.");

  for(int i=30; val && i; --i)
  {
    val /= base;
    buf[i] = "0123456789abcdef"[val % base];
  }

  if(value < 0 && base == 10)
    //make the output negative

  return &buf[i+1];
}

Thanks in advance! :)

[tux4life]

I wrote something equal using strings, look at this snippet :) so you can see how it' done ...

Hope this helps !

[WaltP]

Hello everyone, I'm working on a small assignment where I am supposed to write the code for the itoa function

char* itoa(int Value, int Base);

without using any built-in functions, and where the returned value is allocated on behalf of the caller. Value being the integer to convert, and base being octal, decimal, or hex.

I found this rather simple implementation and I was hoping we could discuss it here to see if the changes I'm making are appropriate/accurate and etc.

OK, have a seat...
1) malloc() -- this will cause memory leaks on each call. Once the function returns, the memory address allocated is lost and can not be returned to the heap. Stick with the static char from the original code.

2)

for(int i=30; val && i; --i)
  {
    val /= base;
    buf[i] = "0123456789abcdef"[val % base];
  }

The first thing you do in the loop is remove the low order digit so if you pass in2765 you would get back 276.

3)

buf[i] = "0123456789abcdef"[val % base];

This is a trick that I personally would avoid -- but that's just me. Create a char* with the character values.
Also, what happens if the base passed in is > 16? This line will cause a lot of trouble. You need to test for proper base range to protect the program this function is used it.

[vmanes]

Lines 3 & 4 - you create the array buf, then again allocate memory to it? Why using malloc() when you can use the C++ new? You're on the right track, as to return the string you need to allocate with new so the memory exists outside the function's stack allocation. Declare buf as a char*.

Lines 6 & 7 - you probably don't need to worry about special case of 0, just let the code set a 0 in the output string, as it would any other value. Otherwise, if you want to do this, you'll need to put the char '0' into the string, not in the way your line 7 does.

Line 10 - check the logic of the boolean operator you're using. Will that really reject anything other than 8, 10, 16?

Line 16 - clever. I'd never seen that done or considered it.

Watch your index usage. You start out with array of 36 elements, your processing loop starts at index 30. Pick a size! Remember that last valid index is size-1, and that position better contain a NULL terminator for the string.

I do find it a bit problematic that you will return the address of a point inside the block of memory allocated, thus orphaning the memory at the beginning of that block.

[AnujSuper9]

Hmmm, ok. Let me make some adjustments.

char* itoa(int val, int base)
{
  new static char* buf[32] = {0}; //1

  //since base can only be octal, decimal or hex
  if (base != 8 && base != 10 && base != 16) //2
    printf("Not a valid base.");

  for(int i=30; val && i; --i)
  {
    val /= base;
    buf[i] = "0123456789abcdef"[val % base]; //3
  }

  if(value == 0)
    //return char 0 //4

  if(value < 0 && base == 10)
    //make the output negative //5

  return &buf[i+1];
}

1. So 'new' here will work? This will allocate the return value on behalf of the caller?
I was worried that if two consecutive itoa() calls were made, and then they were both output, that the first one would be overridden.

2. LOL, duh, stupid mistake. Thanks vmanes. :P

3. And actually, could someone please explain buf[i] = "0123456789abcdef"[val % base];
to me. I found the trick somewhere else, and kind of understand how it works, but I don't exactly understand HOW it works, if you know what I mean.
WaltP, why would you avoid this trick?

4. With the code the way it is, wouldn't I need a special case to account for a value of 0? Otherwise it won't even run the for loop. Additionally, how should a return a char 0?

5. I'm not sure how to make the output negative here exactly.

--Watch your index usage. You start out with array of 36 elements, your processing loop starts at index 30. Pick a size! Remember that last valid index is size-1, and that position better contain a NULL terminator for the string.I changed the array of elements to be 32. This should solve both issues, right?I do find it a bit problematic that you will return the address of a point inside the block of memory allocated, thus orphaning the memory at the beginning of that block.
How would I go about correcting these issues? I'd really like this implementation to be functional as well as optimally efficient.

---
I was getting frustrated with this implementation I was trying above, so I started working on something much much more basic, and therefore probably a lot less efficient, and no doubt soon to be full of problems as well, but seeing your guys' posts here makes me want to make sure this implementation works moreso than the new one I was going to get at. So please bare with me as I try to get the final function for my code. :)

[AnujSuper9]

So I updated my current implementation in the last post. Does anyone else have any suggestions for me?

[vmanes]

Compile and see where the several mistakes still exist.

Line 3 - declaring buf that way doesn't work. You'll need to declare a pointer, then allocate memory to it. I'd also set the last element as the string terminator.

You use the variable i which is declared in the loop at line 9 in your return statement - at that point, i is out of scope. Declare your variable outside the loop (at the beginning of the function?)

Swap lines 11 and 12. As they are, input of 234 at base 10 gives output of 023. You want to strip off and store the lower values, then discard them.

Line 15 - how can val (value - watch that you use the same names!) be anything but 0 at this point? Unless you sent in a really large number.

Line 19 - really, what do you have to do to make the string represent a negative number? Oh, you've destroyed the initial input, so you don't know what it was. Perhaps you need a variable to modify, but keep the input parameter untouched.

[skatamatic]

Your function makes little to no sense to me. Just think about injecting test values into it. Say you pass it 5, base 10:

5 / 10 = 0.5 = 0 (int)
"0123456789abcdef"[0 % 10] = '0'
Well damn. It's already broken and didn't even give me my single digit!

Now try 15
15 / 10 = 1.5 = 1(int)
"0123456789abcdef"[1 % 10] = '1' --->promising start...?
1 / 10 = 0
"0123456789abcdef"[0 % 10] = '0' ----> aww crap!

I think you're going to have to find an alternate method.
And to explain "0123456789abcdef"[val % base]
Basically this takes the base, divides it by the value, spits out the remainder and that servers as the index of the output char in the string previous to the index operator - [].
This works great for single digits by itself:
"0123456789abcdef"[5 % 10] = '5'

But then it can be argued...so does just using the single digit:
"0123456789abcdef"[5] = '5'

I understand what the original author is trying to do by dividing by the base each time to shrink the number (ie access each digit) but it just doesn't seem to work! Unless, perhaps, I'm missing something...

As for the negative:

char * itoa(int iNum, int iBase)
{
        char* buf = new char[32]; 
        int i = 0;
        if (iNum < 0)
            buf[i++] = '-';
        //...Code...
}

I wouldn't start the for loop at 30 though, i would start it at whatever i is. (either 0 or 1)

[AnujSuper9]

Ok, here is my current implementation:

#include <stdio.h>

char* itoa(int value, int base)
{
  static char* buf = new (char [32]); //1
  buf[31] = '\0';

  if (base != 8 && base != 10 && base != 16)
    printf("Not a valid base.");

  int valuecopy;
  valuecopy = value;

  if(value == 0)
    return buf = '0'; //2, return char 0

  int i = 30;
  for(; valuecopy && i; --i)
  {
    buf[i] = "0123456789abcdef"[valuecopy % base];
    valuecopy /= base;
  }

  if(value < 0 && base == 10)
  {
    --i;
    buf[i] = '-'; //3, make the output negative
  }

  return &buf[i+1];
}

1. Is this right? For the memory allocation of the output.

2. Will this return a char 0? I'm not sure how to write this line.

3. As with 2, will this make the output appear negative? Again, not sure how to write this line.

----
@skatamatic: With the lines switched as per vmanes observation, it should make much more sense. And as for starting at 0 or 1 instead of 30, if I did this, than the resulting string would be reversed, no?

[vmanes]

Does it work? Seems to, except for the line 14/15 part. You cannot assign a single character to the array. You want to put a character '0' into the array and then return the address of where that 0 is, similar to your normal return at the end.

Or just put a '0' in the lowest digit position, and let your processing loop overwrite it, if that 's what happens. If input value was 0, be sure to account for the index i.

Experiment!

[AnujSuper9]

If input value was 0, be sure to account for the index i.

What do you mean by this? In my for loop, one of the conditions is valuecopy && i, so if value is 0, valuecopy will be 0, and then it won't enter the for loop at all and continue like normal.

Anyway, your idea for putting 0 in the buffer is great! Why didn't I think of that.

So if I put on line 7 buf[30]='0';
and then just get rid of lines 14 and 15, that would work! Right?

[vmanes]

What do you mean by this? In my for loop, one of the conditions is valuecopy && i, so if value is 0, valuecopy will be 0, and then it won't enter the for loop at all and continue like normal.

Anyway, your idea for putting 0 in the buffer is great! Why didn't I think of that.

So if I put on line 7 buf[30]='0'; and then just get rid of lines 14 and 15, that would work! Right?

Almost right. If input value is 0, what is the value of i when you get to the return statement? Will the address you return correctly point to the character '0' you put at index 30?

[AnujSuper9]

Whoops, I meant for it to say buf[31]='0'; instead of 30.

In which case the return statement should still be ok.

[AnujSuper9]

Ok, I made some more additions and changes, and I think this is perfect. Pending any of your stamp of approval, of course. :)

So, instead of the buffer size of 32, I added a bit to calculate the length of the result string and instead base it on that.

Here it is:

char* itoa(int value, int base)
{
  int valuecopy;
  valuecopy = value;

  int bufsize=1;
  while(valuecopy > 0)
  {
    valuecopy /= base;
    bufsize++;
  }

  valuecopy = value;

  static char* buf = new (char [bufsize+2]); //1
  buf[bufsize+1] = '\0';
  buf[bufsize] = '0';

  if (base != 8 && base != 10 && base != 16)
    printf("Not a valid base.");

  int i = bufsize;
  for(; valuecopy && i; --i)
  {
    buf[i] = "0123456789abcdef"[valuecopy % base];
    valuecopy /= base;
  }

  if(value < 0 && base == 10)
  {
    --i;
    buf[i] = '-';
  }

  return &buf[i+1];
}

[vmanes]

Test, test, then test some more.

It doesn't appear to correctly handle input value 0 or negatives.

Step through the code (by hand or in a debugger) Follow the values.

[AnujSuper9]

Alas, that's actually one of my problems, is that I don't have visual studio on my current machine, which makes it a lot harder to debug this. :(

Though, aha! I think I see the problem.

When I return &buf[i+1] , in the case of negative numbers, it's stripping off the '-' which should be in[i], and in the case of zero, the zero is also in [i], so [i+1] for both of those is wrong.

Also, the original valuecopy check could be negative and mess the whole thing up, so now valuecopy will be the absolute value of value.

So if i change the for loop to a while loop, and put the i-- at the end, it should end with i = i+1. Which would solve the problems I think.

So...

char* itoa(int value, int base)
{
  int valuecopy1, valuecopy2;
  valuecopy1 = value;
  if (valuecopy1 < 0)
    valuecopy1 *= -1;
  valuecopy2 = valuecopy1;

  int bufsize=1;
  while(valuecopy1 > 0)
  {
    valuecopy1 /= base;
    bufsize++;
  }

  static char* buf = new (char [bufsize+2]);
  buf[bufsize+1] = '\0';
  buf[bufsize] = '0';

  if (base != 8 && base != 10 && base != 16)
    printf("Not a valid base.");

  int i = bufsize;
  while(valuecopy2 > 0)
  {
    buf[i] = "0123456789abcdef"[valuecopy2 % base];
    valuecopy2 /= base;
    i--;
  }

  if(value < 0 && base == 10)
  {
    i--;
    buf[i] = '-';
  }

  return &buf[i];
}

[tux4life]

Alas, that's actually one of my problems, is that I don't have visual studio on my current machine, which makes it a lot harder to debug this. :(

You can get a free express edition of Visual Studio here :) ...

[AnujSuper9]

Oh sweet, thanks Tux4Life! :)

Ok cool, I'll try that and see what I can get.

[ArkM]

~0.5 years ago, not so far, far away (on DaniWeb forum):
http://www.daniweb.com/forums/thread148080.html
;)

[AnujSuper9]

That's pretty great ArkM, thanks a bunch!

What do you think of my implementation though? It's a little different, because I'm allocating the space on behalf of the caller instead of passing in the return char string.

But otherwise they seem very similar.