3

（符号なし）整数が与えられた場合、それを10進表現を含む文字列に変換する一般的に最速の方法は何ですか？

それを行うための素朴な方法は、ゼロに達するまで10で繰り返し除算することです。私はこのアプローチが嫌いです。

  • 整数除算を使用します。これは低速であり、一部の統合プラットフォームでは使用できません。
  • プログラマーは後で文字列を反転する必要があります。これにより、必要なメモリ操作の数が2倍になります。

整数を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';
}
4

4 に答える 4

2

コンパイラは定数除数の整数除算を整数乗算に最適化するため、定数による整数除算は乗算を行うのと同じくらい速いと思います。これは、ほとんどの最適化コンパイラによって実行される強力な数学のトリックです。

于 2012-05-07T20:35:31.957 に答える
2

最も単純な（たとえば8ビット）マイクロコントローラーを除くすべてのマイクロコントローラーでの最速のアプローチは、除算を使用することですが、一度に数桁を生成することによって除算の数を減らします。

ここで私の質問への回答に非常に高度に最適化されたコードがあります。Cでそれを使用することは、排除するための簡単な編集であるはずですstd::string-実際の変換で使用されるC++機能はありません。コアは

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;
    }
于 2012-05-07T20:57:31.183 に答える
1

一般的に最も速い方法は、文字列へのポインタの十分な大きさの配列にインデックスを付けることです。1つの配列ルックアップ、1つのポインター逆参照。ただし、メモリの使用量は多くなります...これがエンジニアリングのトレードオフの性質です。どれくらい速いですか？

于 2012-05-07T20:37:04.970 に答える
1

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 */
            }
于 2012-05-07T20:47:12.813 に答える