Быстрое целочисленное преобразование в десятичное целое

Учитывая целое число (без знака), каков, как правило, самый быстрый способ его преобразования в строку, содержащую ее десятичное представление?

Это означает, что вы много раз делитесь на 10, пока не достигнете нуля. Мне не нравится этот подход, потому что он

использует целочисленное деление, которое является медленным и недоступным на некоторых интегрированных платформах.
требует, чтобы программист снова щелкнул строку. Это удваивает количество операций с памятью.

Я подумал о следующем методе преобразования целых чисел в десятичную базу. Это хорошая идея? Как это делается в общих реализациях таких функций, как printf?

#include <stdint.h>

const static uint64_t i64_tab[20] = {
                     1u,
                    10u,
                   100u,
                  1000u,
                 10000u,
                100000u, /* 10^ 5 */
               1000000u,
              10000000u,
             100000000u,
            1000000000u,
           10000000000u, /* 10^10 */
          100000000000u,
         1000000000000u,
        10000000000000u,
       100000000000000u,
      1000000000000000u, /* 10^15 */
     10000000000000000u,
    100000000000000000u,
   1000000000000000000u,
  10000000000000000000u  /* 10^19 */
};

void uint64_to_string(char *out, uint64_t in) {
  int i;
  uint64_t tenpow;
  char accum;

  for (i = 19;i > 0;i--) {
    if (in >= i64_tab[i]) break;
  }

  do {
    tenpow = i64_tab[i];
    accum = '0';

    while (in >= tenpow) {
      in -= tenpow;
      accum++;
    }

    *out++ = accum;

  } while (i --> 0);

  *out = '\0';
}

const static uint32_t i32_tab[10] = {
           1u,
          10u,
         100u,
        1000u,
       10000u,
      100000u, /* 10^ 5 */
     1000000u,
    10000000u,
   100000000u,
  1000000000u, /* 10^9  */
};

void uint32_to_string(char *out, uint32_t in) {
  int i;
  uint32_t tenpow;
  char accum;

  for (i = 9;i > 0;i--)
    if (in >= i32_tab[i]) break;

  do {
    tenpow = i32_tab[i];
    accum = '0';

    while (in >= tenpow) {
      in -= tenpow;
      accum++;
    }

    *out++ = accum;

  } while (i --> 0);

  *out = '\0';
}

Ответы

Ответ 1

Самый быстрый подход для всех, кроме простейших (например, 8-разрядных) микроконтроллеров, - использовать деление, но уменьшать количество делений, генерируя сразу несколько цифр.

Вы найдете очень высоко оптимизированный код в ответах на мой вопрос здесь. Использование его в C должно быть тривиальным редактированием для устранения std::string - в действительном преобразовании нет функций С++. Ядро

while(val>=100)
{
   int pos = val % 100;
   val /= 100;
   *(short*)(c-1)=*(short*)(digit_pairs+2*pos); // or use memcpy
   c-=2;
}
while(val>0)
{
    *c--='0' + (val % 10);
    val /= 10;
}

Я также предоставил оптимизированный код без разделения для 8-разрядных микросов, аналогичный идее, показанной в коде в вопросе, но без циклов. В результате получается много кода:

    if (val >= 80) {
        ch |= '8';
        val -= 80;
    }
    else if (val >= 40) {
        ch |= '4';
        val -= 40;
    }
    if (val >= 20) {
        ch |= '2';
        val -= 20;
    }
    if (val >= 10) {
        ch |= '1';
        val -= 10;
    }

Ответ 2

Я считаю, что целочисленное деление на константу выполняется так же быстро, как умножение, потому что компилятор оптимизирует целочисленное деление на целочисленное умножение для постоянных делителей. Это сложный математический трюк, выполняемый большинством оптимизирующих компиляторов.

Ответ 3

Самый быстрый способ - индексировать в достаточно большой массив указателей на строки. Один массив поиска, один разыменовывающий указатель. Это тяжело для использования памяти, хотя... Что характер инженерных компромиссов. Как быстро достаточно быстро?

Ответ 4

MS версия printf делает это "наивным" способом (после настройки группы переменных на основе необязательных флагов):

            while (precision-- > 0 || number != 0) {
                digit = (int)(number % radix) + '0';
                number /= radix;                /* reduce number */
                if (digit > '9') {
                    /* a hex digit, make it a letter */
                    digit += hexadd;
                }
                *text.sz-- = (char)digit;       /* store the digit */
            }