Implementation of atoi()

Question

I implemented the atoi() function! Here is my code:

int my_atoi(char* pointer)
{
    int result = 0;
    char* pointer1;
    multiplier = 1;
    char sign = 1;

    if(*pointer == '-')
    sign =- 1;  

    pointer1 = pointer;

    while(*pointer != '\0')
    {
        if(*pointer >= '0' && *pointer <= '9')
            multiplier = multiplier * 10;

        pointer = pointer + 1;  
    }

    pointer = pointer1;

    while(*pointer != '\0')
    {       
        if(*pointer >= '0' && *pointer <= '9')
        {
            result = result + ( (*pointer%48)  * multiplier);
            multiplier = multiplier / 10;       
        }

        pointer = pointer+1;
    }

    return (result * sign) / 10;
}

I wonder if there is any way that I can improve my function. I know there is a problem with my function. What if the user wants to convert from char* to int this string: "232-19". What should I do then? Any advice would be really helpful!

Answer 1

Things you could improve

Variables/Initialization

• Where do you declare multiplier? I assume that since it is not declared within the method, it is declared as a global variable. Try to avoid global variables.

  The problem with global variables is that since every function has access to these, it becomes increasingly hard to figure out which functions actually read and write these variables.

  To understand how the application works, you pretty much have to take into account every function which modifies the global state. That can be done, but as the application grows it will get harder to the point of being virtually impossible (or at least a complete waste of time).

  If you don't rely on global variables, you can pass state around between different functions as needed. That way you stand a much better chance of understanding what each function does, as you don't need to take the global state into account.

  So instead of using global variables, initialize the variables in main(), and pass them as arguments to functions if necessary. In this case, I don't see the need for multiplier to be used outside of the function at all, so simply keep it declared within the function.

• sign should be an int, and not a char.

Algorithm

• Right now you are implementing a complicated and hard to follow method of converting a character into a number. The easy way is to have isdigit() do the hard work for you. This also will help you implement the DRY principle.

  while(*pointer != '\0')
  {
      if(*pointer >= '0' && *pointer <= '9')
          multiplier = multiplier * 10;
  
      pointer = pointer + 1;  
  }
  
  pointer = pointer1;
  
  while(*pointer != '\0')
  {       
      if(*pointer >= '0' && *pointer <= '9')
      {
          result = result + ( (*pointer%48)  * multiplier);
          multiplier = multiplier / 10;       
      }
  
      pointer = pointer+1;
  }
  

  See how you have two loops doing almost identical things? Here is how I simplified all of that by using isdigit().

  while (isdigit(*c)) 
  {
      value *= 10;
      value += (int) (*c - '0');
      c++;
  }
  

  You loop through the characters in the string as long as they are digits. For each one, add to the counter you're keeping - the value to add is the integer value of the character. This is done by subtracting the ASCII value of '0' from the ascii value of the digit in question.

• Note that this code doesn't handle overflow. If you pass in "89384798719061231" (which won't fit in an int), the result is undefined. The fix is simple enough, just use a long long int to mitigate against that. We'll still have issues for extremely long numbers, but fixing that so that the function works as intended is a bit more complicated.

Documentation

• Where did all of your comments go? A newer developer would simply gawk at some of your code.

  result = result + ( (*pointer%48)  * multiplier);
  

  Comments can really go a long way into helping other understand your code. Don't go overboard with them though, you will have to balance how much of them to put into your program.

Syntax/Styling

• This looks like a typo.

  if(*pointer == '-')
      sign =- 1;
  

  Add a space for clarity.

  if(*pointer == '-') sign = -1;
  

• You should not be modifying your char* you accept as a parameter into the function. Therefore, declare the parameter as constant.

  int my_atoi(const char* pointer)
  

• Use more shorthand operators.

  pointer++;         // same as pointer = pointer+1;
  multiplier /= 10;  // same as multiplier = multiplier / 10;
  multiplier *= 10;  // same as multiplier = multiplier * 10;
  

Final Code

#include <stdio.h>
#include <assert.h>
#include <ctype.h>

long long int my_atoi(const char *c)
{
    long long int value = 0;
    int sign = 1;
    if( *c == '+' || *c == '-' )
    {
        if( *c == '-' ) sign = -1;
        c++;
    }
    while (isdigit(*c))
    {
        value *= 10;
        value += (int) (*c-'0');
        c++;
    }
    return (value * sign);
}

int main(void)
{
    assert(5 == my_atoi("5"));
    assert(-2 == my_atoi("-2"));
    assert(-1098273980709871235 == my_atoi("-1098273980709871235"));
    puts("All good."); // I reach this statement on my system
}

Answer 2

[Edit]

Except for the behavior on error, atoi() is equivalent to (int)strtol(nptr, (char **)NULL, 10). strtol() accepts leading white space. OP's my_atoi(char* pointer) does not. To remedy:

int my_atoi(const char* pointer) {
  while (isspace((unsigned char) *pointer)) {
    pointer++;
  }
  ...

The below does describe a good way to handle INT_MIN.

OTOH, handing values outside [INT_MIN...INT_MAX] is is not defined by the C spec, so some simplifications can be had. See far below.

---

When a string represents INT_MIN, (let's assume 32-bit int) such as "-2147483648", code runs into int overflow attempting to get to calculate 2147483648. A simple way to solver this is rather than finding the positive value and then negating it, embrace the negative side of things. By doing the lion share of the math in the INT_MIN to 0 range, we avoid UB. Down-side: some find this approach more challenging to follow.

Going to a wider integer or unsigned it not always possible as the integer size of "text--> integer" routine may be the maximum size. Strictly speaking unsigned does not always have a wider positive range than int. In any case, all the math can be handled at the desired signed integer size without resorting to other types.

#include <ctype.h>
#include <limits.h>

int my_atoi(const char* pointer) { // good idea to make the `const`
  int result = 0;
  while (isspace((unsigned char) *pointer)) {
    pointer++;
  }
  char sign = *pointer;
  if (*pointer == '-' || *pointer == '+') {  // text could lead with a '+'
    pointer++;
  }
  int ch;
  // isdigit() expects an unsigned char or EOF, not char
  while ((ch = (unsigned char)(*pointer)) != 0) {
    if (!isdigit(ch)) break;
    ch -= '0';
    // Will overflow occur?
    if ((result < INT_MIN/10) || 
        (result == INT_MIN/10  && ch > -(INT_MIN%10))) Handle_Overflow(); 
    result *= 10;
    result -= ch;  // - , not +
    pointer++;
    }
  if (sign != '-') {
    if (result < -INT_MAX) Handle_Overflow();
    result = -result;
  }
  return result;
}

Notes:

pointer%48 is confusing. What is special about 48? If you mean '0', then use pointer % '0'.

"string: "232-19". What should I do then?" Recommend stopping conversion at "232" and returning the value 232. Could set errno, but the typical atoi() function does not do too much error handling.

On overflow, setting errno, could happen, but again, typical atoi() function does not do too much error handling. Suggest simple returning INT_MAX or INT_MIN.

If you want better error handling, change to something like the following and set an error status.

int my_atoi(const char *s, int *ErrorCode);

or location where things ended. If this are good, they ended at the '\0'.

int my_atoi(const char *s, const char **endptr);  

---

[Edit] Simplified: Removed out-of-range detection as C spec allows that. "If the value of the result cannot be represented, the behavior is undefined.

int my_atoi(const char* pointer) {
  int result = 0;
  while (isspace((unsigned char) *pointer)) {
    pointer++;
  }
  char sign = *pointer;
  if (*pointer == '-' || *pointer == '+') {
    pointer++;
  }
  while (isdigit((unsigned char)*pointer)) {
    result = result*10 - (*pointer++ - '0');
    }
  if (sign != '-') {
    result = -result;
  }
  return result;
}

Answer 3

  char sign = *pointer;
  if (*pointer == '-' || *pointer == '+') {
    pointer++;
  }

Why de-referencing "pointer" three times? One time is enough:

  char sign = *pointer;
  if (sign == '-' || sign == '+') {
    pointer++;
  }

Answer 4

if you are ok with recursion then code could be shortened to one below

#include <string.h>
#include <math.h>
#include <stdbool.h>

int natural_number(const char* string) {
    int index = strlen(string) - 1;
    int number = pow(10, index) * (*string - '0');

    return (index == 0) ? number : number + natural_number(string + 1);
}

int my_atoi(const char* string) {
    int sign = (*string == '-') ? -1 : 1;
    int offset = (*string == '-') ? 1 : 0;

    return sign * natural_number(string + offset);
}

/* test cases */
my_atoi("-100") == -100;
my_atoi("0") == 0;
my_atoi("100") == 100;

Stack exhaustion could be mitigated by -foptimize-sibling-calls compiler flag, that being supported by both GCC and Clang compilers.

Update:

As noted by Roland Illig implementation does not handle malformed input. If it is desired closelly follow atoi semantics then next code should be fine _{don't forget set Compile Options to one in comments}.

int digit(char symbol) {
    return symbol - '0';
}

/* tail call optimized */
int natural_number_tc(const char* string, int number) {
    return !isdigit(*string)
           ? number
           : natural_number_tc(string + 1, 10 * number + digit(*string));
}

int natural_number(const char* string) {
    return natural_number_tc(string, 0);
}

const char* left_trim_tc(const char* string, const char* symbol) {
    return !isspace(*string)  ? symbol : left_trim_tc(string + 1, symbol + 1);
}

const char* left_trim(const char* string) {
    return left_trim_tc(string, string);

}

int my_atoi(const char* string) {
    const char* symbol = left_trim(string);
    int sign = (*symbol == '-') ? -1 : 1;
    size_t offset = (*symbol == '-' || *symbol == '+') ? 1 : 0;

    return sign * natural_number(symbol + offset);
}

This is still chux's code where loops replaced with recursion

int result = 0;
while (isdigit((unsigned char)*pointer)) {
  result = 10 * result + (*pointer - '0');
  pointer++;
}

// VS

int loop(const char* pointer, int result) {
  return !isdigit((unsigned char)*pointer)
         ? result
         : loop(pointer + 1, 10 * result + (*pointer - '0'))
}

Answer 5

For a exercise in leetcode, wrote following impl: atoi cpp code

    class Solution {
private:
    bool checkMin(int a,  int b=10, int c=0, int min_val=INT_MIN) {
        /*
        accepts a*b + c, min
        a>min; b>min; c>min
        check a*b+c > min or not
        b>0; a<0 -ive; c<0
        a!=0
        */

        min_val = min_val  -c;

        //std::cout<<"new min input:  "<<a <<" , "<< c<<"   iter: "<<b << "    "<<min_val <<std::endl;

        //compare with a now
        if(a<min_val)
            return false;
        int cur_prod = 0;
        if(a==0)
            return true;
        for(;b>1;b--) {
            cur_prod += a;
           int curr_diff = min_val-cur_prod; 
            /*
            subtraction possible because 
                min_val<prod,
                min_val-prod<prod-prod 
                min_val-prod<0 ---1
                prod<0
                -prod>0
                min_val+(-prod )> min_val+0 [x+ (+ive quantity)>x ]
                min_val-prod>min_val --2
                from 1, 2
                min_val< min_val-prod < 0 ---3
                from 3, min_val-prod can be expressed in integer

            check if curr_diff still can hold a deduction of a
            which means: curr_diff<a should hold, for a further a deduction in prod
                         -5, -6
                            for ex of min_val = 59, a = -6 at b = 2 (9th iteration) prod = -54
                            you can't add -6 now, since it will cross definable limit
            only b-1 iterations
            because at i-1 th iteration, ith product formation is checked
            */
            //std::cout<<"check function for input:  "<<a <<" , "<< c<<"   iter: "<<b << " prod now = "
                    //<< cur_prod << "   diff = " <<curr_diff<<"  is curr_dif<a "<<(curr_diff<a)<<std::endl;
            if(curr_diff>a) {
                //std::cout<<" not possible"<<std::endl;
                return false;
            }

        }
        return true;
    }

    bool checkMax(int a,  int b=10, int c=0, int max_val=INT_MAX) {
        /*
        accepts a*b + c, min
        a<max; b<max; c<max
        check a*b+c < max or not
        b>0; a>0, c>0
        */

        max_val = max_val  -c;

        //std::cout<<"new max input:  "<<a <<" , "<< c<<"   iter: "<<b << "    "<<max_val <<std::endl;

        //compare with a now
        if(a>max_val) return false;
        int cur_prod = 0;
        if(a==0) return true;
        for(;b>1;b--) {
            cur_prod += a;
           int curr_diff = max_val-cur_prod; 
            /*
            subtraction possible because 
                max_val>prod,
                max_val-prod>prod-prod 
                max_val-prod>0 ---1
                prod>0
                -prod<0
                max_val+(-prod )< max_val+0 [x+ (-ive quantity)<x ]
                max_val-prod<max_val --2
                from 1, 2
                0< max_val-prod < max_val ---3
                from 3, max_val-prod can be expressed in integer

            check if curr_diff still can hold a increment of a
            which means: curr_diff>a should hold, for a further a deduction in prod
                         5>6 fails
                            for ex of max_val = 59, a = 6 at b = 2 (9th iteration) prod = 54
                            you can't add 6 now, since it will cross definable limit
            only b-1 iterations
            because at i-1 th iteration, ith product formation is checked
            */
            //std::cout<<"check function for input:  "<<a <<" , "<< c<<"   iter: "<<b << " prod now = "
            //        << cur_prod << "   diff = " <<curr_diff<<"  is curr_dif<a "<<(curr_diff>a)<<std::endl;
            if(curr_diff<a) {
                //std::cout<<" not possible"<<std::endl;
                return false;
            }

        }
        return true;
    }

public:
    int myAtoi(string str) {
      //code to trim string
      int i =0, end=str.length()-1;
      //std::cout<<i<<"    "<<end<<std::endl;
      while(i<end && str.at(i)==' ') {i++;continue;}
      while(end>-1 && str.at(end)==' ') {end--;continue;}  


      if(end<i) return 0;

      int sign=1;
      if(str.at(i)=='-') {sign = -1; i++;}
      else if(str.at(i)=='+') {i++;}


      string tr_str = str.substr(i, end-i+1);

      int num = 0;

       for(char& digit : tr_str) {
        if(digit<'0' || digit>'9') return num; // not convertable character - exit
        int c= digit-'0';
        if(sign==-1) {
            //std::cout<<"Evaluating "<<c<<std::endl;
            //number cannot be lower than INT_MIN
            // do a check of num * 10 - c 
            //num<0 already

            if(checkMin(num, 10, -c, INT_MIN))
                num = num*10 -c;
            else {
                num = INT_MIN;
                break;
            }
            //std::cout<<"number is"<<num<<std::endl;
        }
        else {
            if(checkMax(num, 10, c, INT_MAX))
                num = num*10 +c;
            else {
                num = INT_MAX;
                break;
            }
            //std::cout<<"number is"<<num<<std::endl;
        }
       }
       return num;


    }
};