1

我希望能够将一个字符指针作为输入，该指针指向一个以 2 到 16 为基数的数字，并作为第二个参数，该数字所在的基数，然后将其转换为以 2 为基数的表示形式。整数可以是任意长度。我的解决方案现在执行 atoi() 函数的功能，但如果查找表解决方案是可能的，我纯粹出于学术兴趣而感到好奇。

我发现这对于二进制、八进制和十六进制都很简单。我可以简单地为每个数字使用查找表来获取一系列位。例如：

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

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

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

但是，我的问题是我想为奇数基数（例如基数 10）执行此查找表方法。我知道我可以像 atoi 那样编写算法并执行一堆乘法和加法，但是对于这个特定问题我我想看看我是否可以用查找表来做到这一点。不过，以 10 为底的情况肯定不是那么明显。我很好奇是否有人有任何聪明的方法来弄清楚如何为 Base X -> Base 2 生成通用查找表。我知道对于 base 10，你不能一次只给它一个数字，所以解决方案可能必须一次查找一组数字。

我知道乘法和加法解决方案，但由于这些是任意长度的数字，所以乘法和加法操作不是免费的，所以如果可能的话，我想避免它们。

4

7 回答 7

4

m您将不得不使用带有返回位的基本b符号输入宽度的查找表，n以便

n = log2(b) * m

对于正整数b和。因此，如果不是 2 的幂，将没有（简单）查找表解决方案。nmb

我不认为有解决办法。以下以 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 回答
4

在不是 2 的幂的基础中，这是不可能转换为 base-2 的。基数为 8（和 16）的原因是转换的工作方式如下：

八进制 ABC = 8^2*A + 8^1*B + 8^0*C（十进制）
          = 0b10000000*A + 0b1000*B + C（二进制）

因此，如果您有 A = (0b000 到 0b111) 的查找表，则乘法始终是 1 和一些尾随零，因此乘法很简单（只是左移）。

但是，请考虑 10 的“奇数”底数。当您查看 10 的幂时：

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

您会注意到乘法永远不会变得简单，因此无论您对它们进行多大的分组，都不能有任何查找表并进行位移和或运算。它总是会重叠。您可以做的最好的事情是有一个如下形式的查找表： (a,b) 其中 a 是数字位置，b 是数字 (0..9)。然后，您只需要添加 n 个数字，而不是乘以和添加 n 个数字（加上查找表的内存成本）

于 2009-04-21T20:56:52.357 回答
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;
}

当然，您应该注意可能出现的错误（不连贯的输入：base 2 和输入字符串 'af12'）或任何其他异常情况。

于 2009-04-21T20:27:51.257 回答
2

弦有多大？您可以通过执行以下操作将乘法加法转换为查找加法：

  • 将数字 0-9, 10, 20, 30, 40, ... 90, 100, 200, ... 900, 1000, 2000, ... , 9000, 10000, ... 存储在目标库中桌子。
  • 对于从最右边开始的每个字符，适当地索引到表中并将其添加到运行结果中。

当然，我不确定这实际上会表现如何，但这是一个想法。

于 2009-04-21T20:45:48.297 回答
0
  • 从运行计数 0 开始。
  • 对于字符串中的每个字符（从左到右阅读）
    • 将计数乘以基数。
    • 将字符转换为 int 值（0 到基数）
    • 将字符值添加到运行计数。
于 2009-04-21T20:30:28.627 回答
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 回答