Convert integer to string without access to libraries

Question

I recently read a sample job interview question:

Write a function to convert an integer to a string. Assume you do not have access to library functions i.e., itoa(), etc...

How would you go about this?

Dialogize

homework? What would you do to write an integer in base 7? The computer has to do the same (in base 10) – Viticulture

atoi() is even more fun because you have to handle leading whitespace, the unary plus or minus, and both positive and negative overflow (among other things). – Pressman

Answer 1

fast stab at it: (edited to handle negative numbers)

int n = INT_MIN;
char buffer[50];
int i = 0;

bool isNeg = n<0;

unsigned int n1 = isNeg ? -n : n;

while(n1!=0)
{
    buffer[i++] = n1%10+'0';
    n1=n1/10;
}

if(isNeg)
    buffer[i++] = '-';

buffer[i] = '\0';

for(int t = 0; t < i/2; t++)
{
    buffer[t] ^= buffer[i-t-1];
    buffer[i-t-1] ^= buffer[t];
    buffer[t] ^= buffer[i-t-1];
}

if(n == 0)
{
    buffer[0] = '0';
    buffer[1] = '\0';
}   

printf(buffer);

Menswear

About to suggest the same thing. Put in string and reverse string. – Darvon

This fails to handle INT_MIN correctly on two's complement machines. – Domesticity

How to handle the situation when base equals 16? – Pomfret

@Pomfret best way without complicating things will be to convert it to decimal & do the same . – Cobble

This implementation also will fail when n is 0 (zero). – Foilsman

Some comments to explain what's going on could make it easier to understand. – Ries

whats going on here:for(int t = 0; t < i/2; t++) { buffer[t] ^= buffer[i-t-1]; buffer[i-t-1] ^= buffer[t]; buffer[t] ^= buffer[i-t-1]; } – Colitis

@Colitis it reverses the buffer... it's been a while since looking at this :) – Menswear

-n is UB when n == INT_MIN. – Senlac

Answer 2

A look on the web for itoa implementation will give you good examples. Here is one, avoiding to reverse the string at the end. It relies on a static buffer, so take care if you reuse it for different values.

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];

}

Prominence

This implementation will fail when val is 0 (zero). – Foilsman

This is clever. I liked it. – Conakry

It also does not handle negative numbers, but props for being short. – Yearly

Answer 3

The algorithm is easy to see in English.

Given an integer, e.g. 123

1. divide by 10 => 123/10. Yielding, result = 12 and remainder = 3

2. add 30h to 3 and push on stack (adding 30h will convert 3 to ASCII representation)

3. repeat step 1 until result < 10

4. add 30h to result and store on stack

5. the stack contains the number in order of | 1 | 2 | 3 | ...

Atwekk

It's way better to add '0', rather than magical hex constants that happen to be correct in a common encoding. No need to tie code to ASCII when that's not necessary. – Claud

Adding '0' is tying the code to ASCII - you're assuming that '0'..'9' are laid out in order for you. Adding 0x30 produces ASCII output regardless of the compiler's codeset. Adding '0' produces the same output if the compiler's codeset is ASCII, and potentially garbled output otherwise. Having said that, I'd replace my compiler if it didn't use ASCII values for character constants! – Stricture

@NicholasWilson C standard requires that number digits are laid out in order for both; source and execution character sets. – Timtima

Answer 4

I would keep in mind that all of the digit characters are in increasing order within the ASCII character set and do not have other characters between them.

I would also use the / and the% operators repeatedly.

How I would go about getting the memory for the string would depend on information you have not given.

Acicula

Why the downvotes? The relationship between digit values is not ASCII-specific. It's required by the C standard. This answer is not so good, but I think it's intentionally vague since the question was homework. +1 to compensate for ridiculous downvotes. – Batt

I suspect the downvotes because I didn't write any code. I didn't write any code because it seemed like either a homework question or the type of question which anyone interviewing for a job as a C programmer should have been able to answer. – Acicula

@R. It is not your job to "undo" other peoples' right to vote. – Crumpler

I don't think it's unreasonable to vote based on a feeling that the current score is either too high or too low; naively, I would expect lots of people do that. Of course this seems like a discussion more appropriate for meta, so if you think it merits further discussion, maybe open a question there..? – Batt

@R: In reply to your first post stating that the answer was "not so good", that was intentional because I highly suspected that the question was someone's homework. The intent was to provide enough guidance for them to implement it themselves, without doing it for them. Thanks for the neutralizing vote. – Acicula

@LightnessRacesinOrbit It's every users job to use their own vote effectively to promote useful information while burying garbage. – Clisthenes

@MickLH: To promote what they consider to be useful information while burying what they consider to be garbage. When you vote solely to undo someone else's vote, you are in wilful counteraction to the purpose of the voting system that you have just described. – Crumpler

Answer 5

Assuming it is in decimal, then like this:

   int num = ...;
   char res[MaxDigitCount];
   int len = 0;
   for(; num > 0; ++len)
   {
      res[len] = num%10+'0';
      num/=10; 
   }
   res[len] = 0; //null-terminating

   //now we need to reverse res
   for(int i = 0; i < len/2; ++i)
   {
       char c = res[i]; res[i] = res[len-i-1]; res[len-i-1] = c;
   }   

Westnorthwest

This does not handle negative numbers and MaxDigitCount needs to be MaxDigitCountPlusTwo to account for the unary minus and the null terminator. – Pressman

This implementation also will fail when num is 0 (zero). – Foilsman

Answer 6

An implementation of itoa() function seems like an easy task but actually you have to take care of many aspects that are related on your exact needs. I guess that in the interview you are expected to give some details about your way to the solution rather than copying a solution that can be found in Google (http://en.wikipedia.org/wiki/Itoa)

Here are some questions you may want to ask yourself or the interviewer:

• Where should the string be located (malloced? passed by the user? static variable?)
• Should I support signed numbers?
• Should i support floating point?
• Should I support other bases rather then 10?
• Do we need any input checking?
• Is the output string limited in legth?

And so on.

Parasiticide

why would itoa handle floating point numbers? itoa is Integer to ASCII – Menswear

I just wanted to make a point. In an interview, the questions you raise and your way to the solutions are important just like the code. The code of-course should be perfect. – Parasiticide

Answer 7

The faster the better?

unsigned countDigits(long long x)
{
    int i = 1;
    while ((x /= 10) && ++i);
    return i;
}
unsigned getNumDigits(long long x)
{
    x < 0 ? x = -x : 0;
    return
        x < 10 ? 1 :
        x < 100 ? 2 :
        x < 1000 ? 3 :
        x < 10000 ? 4 :
        x < 100000 ? 5 :
        x < 1000000 ? 6 :
        x < 10000000 ? 7 :
        x < 100000000 ? 8 :
        x < 1000000000 ? 9 :
        x < 10000000000 ? 10 : countDigits(x);
}
#define tochar(x) '0' + x
void tostr(char* dest, long long x)
{
    unsigned i = getNumDigits(x);
    char negative = x < 0;
    if (negative && (*dest = '-') & (x = -x) & i++);
    *(dest + i) = 0;
    while ((i > negative) && (*(dest + (--i)) = tochar(((x) % 10))) | (x /= 10));
}

If you want to debug, You can split the conditions (instructions) into
lines of code inside the while scopes {}.

Vitovitoria

I really like your answer but I think it could be improved with a few tweaks. For example char tochar(unsigned short from) can be optimised: inline char tochar(unsigned char from) { if (from > 9) return '0'; return '0' + from; } The edge case could be removed in this particular example since you are sure you will always pass to tochar numbers from 0 to 9. – Attendance

@Attendance That's such an old answer of mine, so believe when I say that I've thought exactly the same thing the moment I saw my answer now! Haha.. Now I've edited it including some other things too since it mentioned "no libraries" and looks like I had blindly used calloc here 2 years ago which obviously needs a library as I can recall~ So, thank you. now it is even better. :) – Vitovitoria

Answer 8

Convert integer to string without access to libraries

Convert the least significant digit to a character first and then proceed to more significant digits.

---

Normally I'd shift the resulting string into place, yet recursion allows skipping that step with some tight code.

Using neg_a in myitoa_helper() avoids undefined behavior with INT_MIN.

// Return character one past end of character digits.
static char *myitoa_helper(char *dest, int neg_a) {
  if (neg_a <= -10) {
    dest = myitoa_helper(dest, neg_a / 10);
  }
  *dest = (char) ('0' - neg_a % 10);
  return dest + 1;
}

char *myitoa(char *dest, int a) {
  if (a >= 0) {
    *myitoa_helper(dest, -a) = '\0';
  } else {
    *dest = '-';
    *myitoa_helper(dest + 1, a) = '\0';
  }
  return dest;
}

void myitoa_test(int a) {
  char s[100];
  memset(s, 'x', sizeof s);
  printf("%11d <%s>\n", a, myitoa(s, a));
}

Test code & output

#include "limits.h"
#include "stdio.h"

int main(void) {
  const int a[] = {INT_MIN, INT_MIN + 1, -42, -1, 0, 1, 2, 9, 10, 99, 100,
      INT_MAX - 1, INT_MAX};
  for (unsigned i = 0; i < sizeof a / sizeof a[0]; i++) {
    myitoa_test(a[i]);
  }
  return 0;
}

-2147483648 <-2147483648>
-2147483647 <-2147483647>
        -42 <-42>
         -1 <-1>
          0 <0>
          1 <1>
          2 <2>
          9 <9>
         10 <10>
         99 <99>
        100 <100>
 2147483646 <2147483646>
 2147483647 <2147483647>

Senlac

Answer 9

I came across this question so I decided to drop by the code I usually use for this:

char *SignedIntToStr(char *Dest, signed int Number, register unsigned char Base) {
    if (Base < 2 || Base > 36) {
        return (char *)0;
    }
    register unsigned char Digits = 1;
    register unsigned int CurrentPlaceValue = 1;
    for (register unsigned int T = Number/Base; T; T /= Base) {
        CurrentPlaceValue *= Base;
        Digits++;
    }
    if (!Dest) {
        Dest = malloc(Digits+(Number < 0)+1);
    }
    char *const RDest = Dest;
    if (Number < 0) {
        Number = -Number;
        *Dest = '-';
        Dest++;
    }
    for (register unsigned char i = 0; i < Digits; i++) {
        register unsigned char Digit = (Number/CurrentPlaceValue);
        Dest[i] = (Digit < 10? '0' : 87)+Digit;
        Number %= CurrentPlaceValue;
        CurrentPlaceValue /= Base;
    }
    Dest[Digits] = '\0';
    return RDest;
}
#include <stdio.h>
int main(int argc, char *argv[]) {
    char String[32];
    puts(SignedIntToStr(String, -100, 16));
    return 0;
}

This will automatically allocate memory if NULL is passed into Dest. Otherwise it will write to Dest.

Cirrhosis

Answer 10

Here's a simple approach, but I suspect if you turn this in as-is without understanding and paraphrasing it, your teacher will know you just copied off the net:

char *pru(unsigned x, char *eob)
{
    do { *--eob = x%10; } while (x/=10);
    return eob;
}

char *pri(int x, char *eob)
{
    eob = fmtu(x<0?-x:x, eob);
    if (x<0) *--eob='-';
    return eob;
}

Various improvements are possible, especially if you want to efficiently support larger-than-word integer sizes up to intmax_t. I'll leave it to you to figure out the way these functions are intended to be called.

Batt

I think you meant pru where you've written fmtu, right? Also, those names are nasty. Are they meant to be understood as 'print unsigned', 'print integer' and 'format unsigned'? Also, this supposes a fixed-length string or memory buffer, since it's not handling the NUL character, and also that the buffer is long enought to be traversed backwards. You should note all this restrictions as a comment or more semantical identifiers in your code. – Heptavalent

*--eob = x%10; is wrong. -x potential UB, no null character for a string. – Senlac

Answer 11

Slightly longer than the solution:

static char*
itoa(int n, char s[])
{
    int i, sign;

    if ((sign = n) < 0)  
        n = -n;        

    i = 0;

    do 
    {      
        s[i++] = n % 10 + '0';  
    } while ((n /= 10) > 0);   

    if (sign < 0)
        s[i++] = '-';

    s[i] = '\0';
    reverse(s);

    return s;
} 

Reverse:

int strlen(const char* str)
{
   int i = 0;
   while (str != '\0')
   {
       i++;
       str++;
   }

   return i;
}

static void
reverse(char s[])
{
    int i, j;
    char c;

    for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

And although the decision davolno long here are some useful features for beginners. I hope you will be helpful.

Thalamus

Answer 12

This is the shortest function I can think of that:

• Correctly handles all signed 32-bit integers including 0, MIN_INT32, MAX_INT32.

• Returns a value that can be printed immediatelly, e.g.: printf("%s\n", GetDigits(-123))

Please comment for improvements:

static const char LARGEST_NEGATIVE[] = "-2147483648";

static char* GetDigits(int32_t x) {
    char* buffer = (char*) calloc(sizeof(LARGEST_NEGATIVE), 1);

    int negative = x < 0;
    if (negative) {
        if (x + (1 << 31) == 0) { // if x is the largest negative number
            memcpy(buffer, LARGEST_NEGATIVE, sizeof(LARGEST_NEGATIVE));
            return buffer;
        }
        x *= -1;
    }

    // storing digits in reversed order
    int length = 0;
    do {
        buffer[length++] = x % 10 + '0';
        x /= 10;
    } while (x > 0);

    if (negative) {
        buffer[length++] = '-'; // appending minus
    }

    // reversing digits
    for (int i = 0; i < length / 2; i++) {
        char temp = buffer[i];
        buffer[i] = buffer[length-1 - i];
        buffer[length-1 - i] = temp;
    }
    return buffer;
}

Yearly

Answer 13

//Fixed the answer from [10]

#include <iostream>

void CovertIntToString(unsigned int n1)
{
    unsigned int n = INT_MIN;
    char buffer[50];
    int i = 0;
    n = n1;

    bool isNeg = n<0;
    n1 = isNeg ? -n1 : n1;

    while(n1!=0)
    {
        buffer[i++] = n1%10+'0';
        n1=n1/10;
    }

    if(isNeg)
        buffer[i++] = '-';

    buffer[i] = '\0';

    // Now we must reverse the string
    for(int t = 0; t < i/2; t++)
    {
        buffer[t] ^= buffer[i-t-1];
        buffer[i-t-1] ^= buffer[t];
        buffer[t] ^= buffer[i-t-1];
    }

    if(n == 0)
    {
        buffer[0] = '0';
        buffer[1] = '\0';
    }

    printf("%s", buffer);
}

int main() {
    unsigned int x = 4156;
    CovertIntToString(x);
    return 0;
}

Middleoftheroad

Answer 14

This function converts each digits of number into a char and chars add together in one stack forming a string. Finally, string is formed from integer.

string convertToString(int num){
  string str="";
  for(; num>0;){
    str+=(num%10+'0');
    num/=10;
  }
  return str;
}

Gower

Where does str.push_back come from if not even atoi is available? – Meredithmeredithe