1

入力として、基数 2 から 16 の数値への文字ポインターを取得し、2 番目のパラメーターとして、数値の基数を取得し、それを基数 2 の表現に変換できるようにしたいと考えています。整数は、任意の長さ。私のソリューションは atoi() 関数が行うことを実行するようになりましたが、ルックアップ テーブル ソリューションが可能であるかどうか、純粋に学問的な関心から興味がありました。

これは、2 進数、8 進数、および 16 進数の場合は単純であることがわかりました。一連のビットを取得するには、各桁のルックアップ テーブルを使用するだけです。例えば：

0xF1E ---> (F = 1111) (1 = 0001) (E = 1110) ---> 111100011110

0766 ---> (7 = 111) (6 = 110) (6 = 110) ---> 111110110

1000 ---> ??? ---> 1111101000

ただし、私の問題は、基数 10 のような奇数の基数に対してこのルックアップ テーブル メソッドを実行したいということです。atoi のようにアルゴリズムを記述して、多数の乗算と加算を実行できることはわかっていますが、この特定の問題については「ルックアップテーブルでそれができるかどうかを確認しようとしています。ただし、基数が 10 の場合はそれほど明白ではありません。基数 X -> 基数 2 の一般的なルックアップ テーブルを生成する方法を理解する賢い方法を誰かが持っているかどうか興味がありました。基数 10 の場合、一度に 1 桁ずつ与えることはできないのでソリューションでは、一度に数字のグループを検索する必要がある可能性があります。

乗算と加算のソリューションは認識していますが、これらは任意の長さの数値であるため、乗算と加算の操作は自由ではないため、可能であれば回避したいと考えています。

4

7 に答える 7

4

これは、2の累乗ではない2進数を2進数に変換することはできません。8進数（および16進数）が可能である理由は、変換が機能する方法が次のとおりであるためです。

8進数のABC=8 ^ 2 * A + 8 ^ 1 * B + 8 ^ 0 * C（10進数）
          = 0b10000000 * A + 0b1000 * B + C（バイナリ）

したがって、A =（0b000から0b111）のルックアップテーブルがある場合、乗算は常に1といくつかの後続ゼロによるものであるため、乗算は単純です（左にシフトするだけです）。

ただし、10の「奇数」ベースを考慮してください。10の累乗を見ると、次のようになります。

10 ^ 1 = 0b1010
10 ^ 2 = 0b1100100
10 ^ 3 = 0b1111101000
10 ^ 4 = 0b10011100010000
..等

乗算が単純になることは決してないので、どれだけ大きくグループ化しても、ルックアップテーブルを作成したり、ビットシフトやORを実行したりすることはできません。常に重なります。最善の方法は、次の形式のルックアップテーブルを用意することです。（a、b）ここで、aは数字の位置、bは数字（0..9）です。次に、n個の数値を乗算して加算するのではなく、n個の数値を加算するだけになります（さらにルックアップテーブルのメモリのコスト）

于 2009-04-21T20:56:52.357 に答える
4

ビットを返すm基本bシンボルの入力幅を持つルックアップ テーブルを使用する必要があります。n

n = log2(b) * m

正の整数の場合b、nおよびm. したがって、bが 2 のべき乗でない場合、(単純な) ルックアップ テーブル ソリューションはありません。

私は解決策があるとは思わない。次の基数 10 の例は、その理由を示しています。

65536 = 1 0000 0000 0000 0000

最後の桁を 6 から 5 に変更すると、すべてのビットが反転します。

65535 = 0 1111 1111 1111 1111

そして、入力を最後から処理する場合、ほぼ同じことが成り立ちます。最初の桁を 6 から 5 に変更すると、かなりの数のビットが反転します。

55535 = 0 1101 1000 1111 0000
于 2009-04-21T20:29:49.363 に答える
2

弦の大きさは？次のようなことを行うことで、潜在的に乗算と加算をルックアップと加算に変換できます。

  • 数値 0 ～ 9、10、20、30、40、... 90、100、200、... 900、1000、2000、...、9000、10000、... をターゲット ベースに格納します。テーブル。
  • 右端から始まる文字ごとに、テーブルに適切にインデックスを付け、実行結果に追加します。

もちろん、これが実際にどれだけうまく機能するかはわかりませんが、それは考えです。

于 2009-04-21T20:45:48.297 に答える
2

アルゴリズムは非常に単純です。言語に依存しない場合は次のようになります。

total = 0
base <- input_base
for each character in input:
   total <- total*base + number(char)

C++ の場合:

// Helper to convert a digit to a number
unsigned int number( char ch )
{
   if ( ch >= '0' && ch <= '9' ) return ch-'0';
   ch = toupper(ch);
   if ( ch >= 'A' && ch <= 'F' ) return 10 + (ch-'A');
}
unsigned int parse( std::string const & input, unsigned int base )
{
   unsigned int total = 0;
   for ( int i = 0; i < input.size(); ++i )
   {
      total = total*base + number(input[i]);
   }
   return total;
}

もちろん、考えられるエラー (一貫性のない入力: ベース 2 と入力文字列 'af12') やその他の例外的な条件に注意する必要があります。

于 2009-04-21T20:27:51.257 に答える
0

どのくらい正確である必要がありますか？

あなたが完璧を探しているなら、乗算と加算は本当にあなたの唯一の頼みの綱です。そして、それがあなたのアプリケーションの最も遅い部分であるならば、私は非常に驚かれることでしょう。

桁違いで十分な場合は、ルックアップテーブルを使用して、最も近い2の累乗を見つけます。

例1：1234、2の最も近い累乗は1024です。例2：98765、最も近いは65536です。

桁数を数え、適切な2の累乗に左端の桁を掛けることによってこれを駆動することもできます。これは、左シフトとして実装できます。

例3：98765は5桁で、2から10000の最も近い累乗は8192（2 ^ 13）であるため、結果は9<<13になります。

于 2009-04-21T20:59:40.273 に答える
0

私はあなたの明確なコメントの前にこれを書いたので、おそらくまったく当てはまりません。ルックアップ テーブル アプローチが可能かどうかはわかりません。任意の精度が本当に必要ない場合は、ランタイムを利用してください。

C/C++ ソリューションが受け入れられる場合、次のようなものを探していると思います。エッジケースにはバグが含まれている可能性がありますが、少なくとも正の数に対しては期待どおりにコンパイルおよび動作します。それを実際に機能させることは、読者の練習です。

/*
 * NAME
 *    convert_num - convert a numerical string (str) of base (b) to
 *                  a printable binary representation
 * SYNOPSIS
 *    int convert_num(char const* s, int b, char** o)
 * DESCRIPTION
 *    Generates a printable binary representation of an input number
 *    from an arbitrary base.  The input number is passed as the ASCII
 *    character string `s'.  The input string consists of characters
 *    from the ASCII character set {'0'..'9','A'..('A'+b-10)} where
 *    letter characters may be in either upper or lower case.
 * RETURNS
 *    The number of characters from the input string `s' which were
 *    consumed by this operation.  The output string is placed into
 *    newly allocated storage which is pointed to by `*o' upon successful
 *    completion.  An error is signalled by returning `-1'.
 */
int
convert_num(char const *str, int b, char **out)
{
    int rc = -1;
    char *endp = NULL;
    char *outp = NULL;
    unsigned long num = strtoul(str, &endp, b);
    if (endp != str) { /* then we have some numbers */
        int numdig = -1;
        rc = (endp - str); /* we have this many base `b' digits! */
        frexp((double)num, &numdig); /* we need this many base 2 digits */
        if ((outp=malloc(numdig+1)) == NULL) {
            return -1;
        }
        *out = outp; /* return the buffer */
        outp += numdig; /* make sure it is NUL terminated */
        *outp-- = '\0';
        while (numdig-- != 0) { /* fill it in from LSb to MSb */
            *outp-- = ((num & 1) ? '1' : '0');
            num >>= 1;
        }
    }
    return rc;
}
于 2009-04-21T21:11:29.730 に答える
0
  • 実行カウント 0 から開始します。
  • 文字列内の各文字 (左から右に読む)
    • カウントを基数で乗算します。
    • 文字を int 値に変換します (0 から base)
    • ランニングカウントに文字値を追加します。
于 2009-04-21T20:30:28.627 に答える