Recoding itoa: error on minimum int

Question

I am trying to recode the itoa function which, given a int, will return a string representing its decimal value. So far, the functions works well:

char        *ft_itoa(int n)
{
    char    s[1024];
    int     i;
    int     neg;

    i = 0;
    neg = 0;
    if (n == 0)
        s[i++] = '0';
    if (n < 0)
    {
        n = n * (-1);
        neg = 1;
    }
    while (n != 0)
    {
        s[i++] = (n % 10) + 48;
        n /= 10;
    }
    if (neg)
        s[i++] = '-';
    s[i] = '\0';
    return (ft_strrev(s));
}

Except for the minimum int value, -2147483648. In that case, the function returns:

"-./,),(-*,("

Wich is... weird. Note that ft_strrev will reverse the result and malloc it. Any clues?

EDIT:

There are quite interesting answers here. I am specially interested in the minium size of the buffer. Using limits.h seems to do the trick, but I am not allowed to include other headers than stdlib.h and string.h. I am also limited in three functions, malloc, free and write. However, I did recode strdup and a lot of functions from libc.

Could someone explain why that line would declare the exact amount of memory I need:

char   buf[sizeof(int) * CHAR_BIT / 3 + 3];

Also,

Using unsigned to compute the digits would avoid the problem with INT_MIN. Bug fix for INT_MIN.

Why?

@BLUEPIXY shouldn't the limit be the same on both signs? I don't get that. — qleguennec, Dec 08 '15 at 22:45
zero is included as well in the total range of numbers so there is one less number for the positive signed numbers. — MattSt, Dec 08 '15 at 22:50
@BLUEPIXY Okay, I guess it has to do with the fact that the count of elements is a power of 2, therefore being a pair number, then if you include 0 you can't have the same amount in both sides. Anyway thanks, question answered. — qleguennec, Dec 08 '15 at 22:51
@qleguennec: actually, it depends from the representation of numbers; if you go with sign and magnitude (as floating point generally do) you have the same limit on both sides, but you have two zeroes (+0 and -0); but for integers on any reasonable platform (=> which employs 2's complement arithmetic) you can rest assured that the range is -2^(n-1) ... 2^(n-1)-1 (where n is the size of the integer in bits). — Matteo Italia, Dec 08 '15 at 23:06

chqrlie · Answer 1 · 2015-12-09T03:13:26.577

2

There are several small issues with your code:

The buffer is much too large: including sign and null terminator, 24 bytes should suffice. For absolute portability, an upper bound of sizeof(int)*CHAR_BIT/3 + 3 is correct. Not a bug, but wasteful.
If you store the digits into the buffer from right to left, you don't need the final reverse phase and could call strdup() directly. Simpler and faster.
Using unsigned to compute the digits would avoid the problem with INT_MIN. Bug fix for INT_MIN.
Looping for i >= 10 and storing the final digit separately avoids the special case for 0. Simpler and faster, fewer divisions.
You should use '0' instead of hard coding ASCII value 48. More readable and portable.

Here is a modified version:

#include <limits.h>

char *ft_itoa(int n) {
    char buf[sizeof(int)*CHAR_BIT/3 + 3];
    char *s;
    unsigned int v;

    v = n;
    if (n < 0) {
        v = -v;
    }
    s = buf + sizeof(buf);
    *--s = '\0';
    while (v >= 10) {
        *--s = '0' + v % 10;
        v /= 10;
    }
    *--s = '0' + v;
    if (n < 0)
        *--s = '-';
    return strdup(s);
}

If strdup is not available on your system, it is easy to implement and quite useful if you allocate strings from the heap.

edited Dec 09 '15 at 03:13

answered Dec 09 '15 at 01:55

chqrlie

131,814
10
121
189

Corner case: Using `unsigned`, in general works to cope with `INT_MIN`. Yet C does not specify that `UINT_MAX > INT_MAX`. Odd ball platforms use a sign bit for `int` and have `UINT_MAX == INT_MAX` and `-INT_MIN` is not representable as an `unsigned`. – chux - Reinstate Monica Dec 09 '15 at 02:04
@chux: true but a very theoretical point these days. All odd ball platforms I know that have `UINT_MAX == INT_MAX` also use sign/magnitude representation, and therefore `-INT_MIN` is representable as an `unsigned`. I'd be interested to see and operate your vintage DS9K for fun `;-)`. – chqrlie Dec 09 '15 at 02:23
@chux: I was expecting a more general remark such as: *you assume 2's complement*. Indeed `v = -v` avoids integer overflow but might not produce the expected value on (hypothetical) non 2's complement hardware. – chqrlie Dec 09 '15 at 02:26
In looking over source coded for highly portable, came across the the summing technique on the negative side of `int`, rather than the positive side. The useful attribute is that since it does not use `unsigned` at all, that type's properties compared to `int` are moot. Some find it more difficult to follow, but it does work – chux - Reinstate Monica Dec 09 '15 at 02:38
How is 2^63 relevant to this? – M.M Dec 09 '15 at 02:40
@M.M: 2^63 is just a silly practical limit, I guess I should use `sizeof(int)*CHAR_BIT/3 + 3` for the buffer size. – chqrlie Dec 09 '15 at 03:07
@chux: your technique is more portable but relies on C99 that first mandated truncation toward 0 for integer division. Under C89, the sign of `i%10` for negative `i` is implementation defined. – chqrlie Dec 09 '15 at 03:24
Can you explain `sizeof(int)*CHAR_BIT/3 + 3`? What is CHAR_BIT? – qleguennec Dec 09 '15 at 13:19
@qleguennec: `sizeof(int)*CHAR_BIT` is the number of bits in an `int`. 3 bits encode 8 different values, which is less than 10. hence `sizeof(int)*CHAR_BIT/3 + 1` is an upper bound for the number of decimal digits. Add 1 for the `'\0'` and 1 for the minus sign. This is an upper bound, for 32 bit ints, `4*8/3+3` = `13`, whereas `-2147483648\0` fits in just `12` bytes. – chqrlie Dec 09 '15 at 14:28

score 1 · Answer 2 · edited May 23 '17 at 12:23

1

Avoid int overflow (if (n < 0) { n = n * (-1); which caused OP's problem) and embraced the dark (negative) side. Since there are more negative int than positive ones, sum on the negative side.

#include <limits.h>
char *ft_itoa(int n) {
  char s[50];
  // char s[1024];
  int i;
  int neg;

  i = 0;
  neg = 0;
  //if (n == 0)          // special case not need with do loop
  //    s[i++] = '0';

  if (n < 0) {           // Insure n is _not_ positive
    // n = n * (-1);
    neg = 1;
  } else {
    n = -n;              // no overflow possible here
  }
  // while (n != 0)
  do {
    // s[i++] = (n % 10) + 48;
    s[i++] = '0' - (n % 10);   // subtract
    n /= 10;
  } while (n);
  if (neg) s[i++] = '-';
  s[i] = '\0';
  return strdup(strrev(s));
}

For a cleaned-up version

#include <limits.h>

// Compute max size need to represent an `int`
#define INT_DEC_SIZE (sizeof (int)*CHAR_BIT/3 + 3)

char *ft_itoa(int n) {
  char s[INT_DEC_SIZE];
  char *p = &s[sizeof s - 1];
  *p = '\0';
  int i = n;
  if (i > 0) {
    i = -i;
  }
  do {
    p--;
    *p = '0' - (i % 10);
    i /= 10;
  } while (i);
  if (n < 0) *(--p) = '-';
  return strdup(p);
}

INT_DEC_SIZE ref

edited May 23 '17 at 12:23

Community

1
1

answered Dec 09 '15 at 02:00

chux - Reinstate Monica

143,097
13
135
256

1

Using `static` persistent memory is **perverse!** The OP explicitly says the result is allocated, why remove this feature and introduce potential hard to find bugs? – chqrlie Dec 09 '15 at 02:09
@chqrlie Did not notice OP's `strrev()` with `malloc()`. Code amended. – chux - Reinstate Monica Dec 09 '15 at 02:21
You should include `` for `CHAR_BIT` in the cleaned-up version – chqrlie Dec 09 '15 at 03:00
@chqrlie My compile pick-up up `CHAR_BIT` when `stdlib.h` was included. Agree `` is the better header file. – chux - Reinstate Monica Dec 09 '15 at 03:27
Although `strdup` is not a standard function, it is usually declared in `` so both are needed. – chqrlie Dec 09 '15 at 03:35

Recoding itoa: error on minimum int

2 Answers2