Interview Question: implement itoa

Implementing itoa function is a popular interview question. Classic approach is use divide operation. But is it really BORRING!
Let`s implement something more interesting with completely different algorithm.
int values are stored as binaries in memory. Whole value is sum of digit * its value. Value for first digit is 1, 2 for second, 4 for third, 8, 16, 32, 64, etc.
Following code converts binary number in printable decemal => it is itoa

itoa implemented as CustomITOA. All another function are just a helpers. Only one intresting thing is SymbolicAdd functions. It does Add operation for numbers represented by strings.
Limitations: this itoa do not have radix parameter.
This code was created just for fun after reading discussion from developers.org.ua site.

    7 #define CHARBUFF_SIZE 15

    8 

    9 //asci code for '0'

   10 #define ASCII_ZERO 0x30

   11 

   12 //represent result of adding of two symbols,

   13 //e.g. 8 + 9 = 7 and shift for next register

   14 struct SymbolAddResult

   15 {

   16     char symb;

   17     bool shift;

   18 };

   19 

   20 SymbolAddResult num_line[] = {

   21     {'0', false}, {'1', false}, {'2', false}, {'3', false}, {'4', false},

   22     {'5', false}, {'6', false}, {'7', false}, {'8', false}, {'9', false},

   23     {'0', true}, {'1', true}, {'2', true}, {'3', true}, {'4', true},

   24     {'5', true}, {'6', true},{'7', true}, {'8', true}, {'9', true}

   25 };

   26 

   27 //return position in num_line array,

   28 //beware, s1 and s2 should be numbers only!!!

   29 inline int AddChars(char s1, char s2)

   30 {

   31     return s1 - ASCII_ZERO + s2 - ASCII_ZERO;

   32 }

   33 

   34 inline char* GetLastSymb(char* param)

   35 {

   36     while(0 != *param)

   37         ++param;

   38     return --param;

   39 }

   40 

   41 //reslt = param1 + param2 where all parameters are symbols

   42 // e.g. "12"+ "36" = "48"

   43 void SymbolicAdd(char* reslt, char* param1, char* param2 )

   44 {

   45     //error processing is absent for parameters,

   46     //CustomITOA use it only and it can not pass wrong strings.

   47     char buff[CHARBUFF_SIZE];

   48     buff[CHARBUFF_SIZE -1] = 0;

   49     int free_cell = CHARBUFF_SIZE -2;

   50     char *curr1 = GetLastSymb(param1);

   51     char *curr2 = GetLastSymb(param2);

   52     bool shift = false;

   53     //param1 and param2 can have different length. So add overlapping

   54     //part first

   55     while(curr1 >= param1 && curr2 >= param2)

   56     {

   57         int localSum = AddChars(*curr1, *curr2);

   58         if(shift)//shift from previous operation

   59             ++localSum;

   60         shift = num_line[localSum].shift;

   61         buff[free_cell] = num_line[localSum].symb;

   62         --free_cell;

   63         --curr1;

   64         --curr2;

   65     }

   66     //if param1 is longer than param2 (or vise versa) add these

   67     //characters to sum

   68     char* longpart = NULL;

   69     char* finish = NULL;

   70     //who is longer? longpart will points it and finish will points

   71     //first symbol in the longest string

   72     if(curr1 >= param1)

   73     {

   74         longpart = curr1;

   75         finish = param1;

   76     }

   77     else if(curr2 >= param2)

   78     {   

   79         longpart = curr2;

   80         finish = param2;

   81     }

   82     if(NULL != longpart)

   83     {

   84         while(longpart >= finish)

   85         {

   86             int pos = *longpart - ASCII_ZERO;

   87             if(shift)

   88                 pos++;

   89             buff[free_cell] = num_line[pos].symb;

   90             shift = num_line[pos].shift;

   91             --longpart;

   92             --free_cell;

   93         }

   94     }

   95     else

   96     {

   97         //param1 and param2 have same length, nothing to copy,

   98         //but dont forget about shift and add it as leading 1

   99         if(shift)

  100         {

  101             buff[free_cell] = '1';

  102             free_cell--;

  103         }

  104     }

  105     //copy result from internal buffer to the destination string

  106     for(free_cell++; free_cell < CHARBUFF_SIZE; ++free_cell, ++reslt)

  107         *reslt = buff[free_cell];

  108 }

  109 

  110 char* power_of_two[] =

  111 {

  112     "1","2","4","8", "16","32","64","128",

  113     "256","512","1024","2048","4096","8192","16384","32768",

  114     "65536","131072","262164","524288","1048576","2097152","4194304","8388608",

  115     "16777216","33554432","67108864","134217728","268435456","536870912","1073741824","2147483648",

  116     "4294967296"

  117 };

  118 

  119 //custom itoa implementation limited to radix 10

  120 //idea is: each digit in position N in binary value means

  121 //"add Digit(1 or 0) * 2^N to common sum" 

  122 //lets do it, but use symbol strings instead of binary values

  123 char* CustomITOA(int value, char *dst)

  124 {

  125     bool below_zero = value < 0;

  126     if(below_zero)

  127         value *= -1;

  128 

  129     *dst = '0';

  130     *(dst+1) = 0;

  131     int nbins = sizeof(int) * 8 - 1;

  132     for(int i=0; i < nbins; i++)

  133     {

  134         if(value & 0x1)

  135         {

  136             SymbolicAdd(dst, dst, power_of_two[i]);

  137         }

  138         value = value >> 1;

  139     }

  140     if(below_zero)

  141     {

  142         //add leading "-" to result string

  143         char cbuffer_first = '-';

  144         char cbuffer_second = cbuffer_first;

  145         char* str_cursor = dst;

  146         do

  147         {

  148             cbuffer_second = *str_cursor;

  149             *str_cursor = cbuffer_first;

  150             if(0 == cbuffer_first)

  151                 break;

  152             cbuffer_first = cbuffer_second;

  153             ++str_cursor;

  154         }

  155         while(true);

  156     }

  157     return dst;

  158 }

  159 

  160 //usage sample

  161 int main(int argc, _TCHAR* argv[])

  162 {

  163     int sint = sizeof(int);

  164     char view[255];

  165 

  166     CustomITOA(147483649,view);

  167     CustomITOA(-35,view);   

  168     return 0;

  169 }

ċ
ITOA.cpp
(4k)
Anatoliy Odukha,
Mar 24, 2009, 8:07 AM
Comments