Interview Question: implement itoa

see source code

относительно atoi на интервью, меня поправили, имелось в виду itoa, но назвали ее atoi.
Вопрос про itoa популярен, но реализация через деление не интересна, слишком скучно и просто. Поэтому реализовал без использования умножения и деления, только сложение и работа со строками.

ф-ция получилась короткой - табличка с уже подсчитаными степенями двойки и куча сложений. Почти половину в этом коде занимает реализация добавления первого символа в строку без использованя дополнительного буфера. А весь magic происходит в SymbolicAdd.

char* power_of_two[] =

{

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

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

//custom itoa implementation limited to radix 10

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

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

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

char* CustomITOA(int value, char *dst)

{

    bool below_zero = value < 0;

    if(below_zero)

        value *= -1;

 

    *dst = '0';

    *(dst+1) = 0;

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

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

    {

        if(value & 0x1)

        {

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

        }

        value = value >> 1;

    }

    if(below_zero)

    {

        //add leading "-" to result string

        char cbuffer_first = '-';

        char cbuffer_second = cbuffer_first;

        char* str_cursor = dst;

        do

        {

            cbuffer_second = *str_cursor;

            *str_cursor = cbuffer_first;

            if(0 == cbuffer_first)

                break;

            cbuffer_first = cbuffer_second;

            ++str_cursor;

        }

        while(true);

    }

    return dst;

}

Получилось просто, но SymbolicAdd намного сложнее(детали в сырцах). Что она делает: берет две строки вида "125", "236" и возвращает строку "361", а всередини реализован своеобразный алгоритм сложения в столбик.