How do I fix my `itoa` implementation so it doesn't print reversed output?

Question

I want to convert an integer into a string of numeric characters in C.

I've tried using itoa, but it's non-standard and not provided by my C library.

I tried to implement my own itoa, but it's not working properly:

#include <stdlib.h>
#include <stdio.h>

char *itoa(int val, char *buf, int base)
{
    size_t ctr = 0;
    for( ; val; val /= base )
    {
        buf[ctr++] = '0' + (val % base);
    }
    buf[ctr] = 0;
    return buf;
}

int main(void)
{
    unsigned char c = 201;
    char *buf = malloc(sizeof(c)*8+1);
    itoa(c, buf, 2);
    puts(buf);
    free(buf);
}

It gives reversed output.

For example, if c is 'A' and base is 2, the output is this: 0101101

The output I want it to be is this: 1011010

How do I fix this issue?

---

Similar questions

---

I've already seen this question: Is there a printf converter to print in binary format?

I do not want a printf format specifier to print an integer as binary, I want to convert the binary to a string.

I've already seen this question: Print an int in binary representation using C

Although the answer does convert an integer into a string of binary digits, that's the only thing it can do.

---

Restrictions

---

I want itoa to be able to work with other bases, such as 10, 8, etc. and print correctly (i.e. 12345 translates to "12345" and not to "11000000111001").

I do not want to use printf or sprintf to do this.

I do not care about the length of the string as long is the result is correct.

I do not want to convert the integer into ASCII characters other than numeric ones, with the exception of bases greater than 10, in which case the characters may be alphanumeric.

The answer must fit this prototype exactly:

char *itoa(int val, char *buf, int base);

There may be a function called nitoa that has this prototype and returns the number of characters required to hold the result of itoa:

size_t nitoa(int val, int base);

Kollwitz

Use sprintf() instead of printf() and it will write to a string. – Mandorla

@Mandorla I don't want to use sprintf or printf, and anyway, those don't deal with binary. – Kollwitz

1) Start at the end of the buffer and work backwards. 2) Use a recursive solution that puts a character into the buffer after the recursive call. 3) Use a bit mask that starts at the MSB. 4) Use a temporary array to hold the backwards string, and then copy the string to the output array. 5) Create the backwards string, and then swap characters to reverse the string. – Apportionment

@Apportionment Thanks. Solution 5 would probably work. How exactly would I do that? – Kollwitz

Many previous questions: stackoverflow.com/search?q=%5Bc%5D+convert+int+to+binary+string – Mandorla

Use two indexes, one that starts at 0, the other starts at the end of the string. Swap the characters, increment the start index, decrement the end index. Terminate the loop when the indexes meet in the middle. – Apportionment

Answer 1

How do I fix my itoa implementation so it doesn't print reversed output?

Rather than reverse the string, form it right-to-left. #4 of @user3386109

---

I recommend the helper function also receives in a size.

#include <limits.h>

char* itostr(char *dest, size_t size, int a, int base) {
  // Max text needs occur with itostr(dest, size, INT_MIN, 2)
  char buffer[sizeof a * CHAR_BIT + 1 + 1]; 
  static const char digits[36] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  if (base < 2 || base > 36) {
    fprintf(stderr, "Invalid base");
    return NULL;
  }

  // Start filling from the end
  char* p = &buffer[sizeof buffer - 1];
  *p = '\0';

  // Work with negative `int`
  int an = a < 0 ? a : -a;  

  do {
    *(--p) = digits[-(an % base)];
    an /= base;
  } while (an);

  if (a < 0) {
    *(--p) = '-';
  }

  size_t size_used = &buffer[sizeof(buffer)] - p;
  if (size_used > size) {
    fprintf(stderr, "Scant buffer %zu > %zu", size_used , size);
    return NULL;
  }
  return memcpy(dest, p, size_used);
}

Then to provide memory, use a compound literal.

// compound literal C99 or later
#define INT_STR_SIZE (sizeof(int)*CHAR_BIT + 2)
#define MY_ITOA(x, base) itostr((char [INT_STR_SIZE]){""}, INT_STR_SIZE, (x), (base))

Now you can call it multiple times.

int main(void) {
  printf("%s %s %s %s\n", MY_ITOA(INT_MIN,10), MY_ITOA(-1,10), MY_ITOA(0,10), MY_ITOA(INT_MAX,10));
  printf("%s %s\n", MY_ITOA(INT_MIN,2), MY_ITOA(INT_MIN,36));
  return (0);
}

Output

-2147483648 -1 0 2147483647
-10000000000000000000000000000000 -ZIK0ZK

---

Note: sizeof(c)*8+1 is one too small for INT_MIN, base 2.

Arleenarlen

Macro compound literal is a nice touch. – Griz

As I commented on Implementation of itoa which allocates the string, you can safely do unsigned abs with 0U - a. Also, runtime-variable base is quite inefficient, not letting the compiler use Why does GCC use multiplication by a strange number in implementing integer division?. To handle that, glibc uses switch(base) with the same code for case 8 / 10 / default, getting GCC to make specialized asm loops for those constant bases. code.woboq.org/userspace/glibc/stdio-common/_itoa.c.htm – Jeopardize

@PeterCordes Agree using runtime-variable base is linearly inefficient vs. dedicated base 8,10,16 code. - still same O(). I save "quite inefficient" for when O() is more than needed. Given Is premature optimization really the root of all evil?, a dedicated base 10 (and 16?) would be is a good idea for the "3%". – Arleenarlen

The upper bound on number of digits is small enough that big-O isn't really appropriate; constant factors can easily make as much difference. (Unless we're talking about something ridiculous like repeated-subtraction O(N) instead of repeated-division O(log(N)).) A factor of maybe 2 (rough guess off the top of my head for CPUs like Skylake) is pretty significant to me in a function that's worth caring about tuning at all, and it would be much worse for 64-bit integers on Intel CPUs before Ice Lake. – Jeopardize

Answer 2

This solution works for me:

#include <errno.h>
#include <stdlib.h>
#include <string.h>

#define itoa lltoa
#define utoa ulltoa
#define ltoa lltoa
#define ultoa ulltoa
#define nitoa nlltoa
#define nutoa nulltoa
#define nltoa nlltoa
#define nultoa nulltoa

#define BASE_BIN 2
#define BASE_OCT 8
#define BASE_DEC 10
#define BASE_HEX 16
#define BASE_02Z 36

__extension__
char *ulltoa(unsigned long long val, char *buf, int base)
{
    int remainder;
    char c, *tmp = buf;

    if(base < BASE_BIN)
    {
        errno = EINVAL;
        return NULL;
    }

    do {
        remainder = val % base;
        if(remainder >= BASE_DEC) c = 'a' - BASE_DEC;
        else c = '0';
        *tmp++ = remainder + c;
        val /= base;
    } while(val);

    *tmp = 0;
    return strrev(buf);
}

__extension__
size_t nulltoa(unsigned long long val, int base)
{
    size_t size = 0;

    if(base < BASE_BIN)
    {
        errno = EINVAL;
        return 0;
    }

    if(!val) size++;

    for( ; val; val /= base, size++ );

    return size;
}

__extension__
char *lltoa(long long val, char *buf, int base)
{
    if(val < 0 && base > BASE_BIN)
    {
         val = -val;
         *buf++ = '-';
    }

    return ulltoa(val, buf, base);
}

__extension__
size_t nlltoa(long long val, int base)
{
    size_t size = 0;

    if(val < 0 && base > BASE_BIN)
    {
        val = -val;
        size++;
    }

    return size + nulltoa(val, base);
}

Kollwitz