Преобразовать строку в целое число (не atoi!)

Question

Я хочу иметь в качестве входных данных указатель на число в базе от 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. Я знаю, что для базы 10 вы не можете просто дать ей одну цифру за раз, поэтому Решение, вероятно, придется искать группу цифр за раз.

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

Answer 1

Это невозможно для баз, которые не имеют степеней двойки для преобразования в базу-2. Причина, по которой это возможно для базы 8 (и 16), заключается в том, что преобразование работает следующим образом:

octal ABC = 8^2*A + 8^1*B + 8^0*C (decimal)
          = 0b10000000*A + 0b1000*B + C (binary)

так что если у вас есть таблица соответствия 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 чисел (плюс стоимость памяти для справочной таблицы)

Answer 2

Вам придется использовать справочную таблицу с шириной ввода m base b символов, возвращающих n битов, так что

n = log2(b) * m

для натуральных чисел b, n и m. Поэтому, если b не является степенью двойки, не будет (простого) решения для поиска в таблице.

Я не думаю, что есть решение. В следующем примере с основанием 10 показано, почему.

65536 = 1 0000 0000 0000 0000

Изменение последней цифры с 6 на 5 перевернет все биты.

65535 = 0 1111 1111 1111 1111

И почти то же самое произойдет, если вы обработаете ввод, начиная с конца. Изменение первой цифры с 6 на 5 переворачивает значительное количество бит.

55535 = 0 1101 1000 1111 0000

Answer 3

Насколько велики струны? Вы можете преобразовать умножение-и-добавление в поиск-и-добавление, выполнив что-то вроде этого:

• Сохраните числа 0-9, 10, 20, 30, 40, ... 90, 100, 200, ... 900, 1000, 2000, ..., 9000, 10000, ... в целевом объекте. база в таблице.
• Для каждого символа, начиная с самого правого, внесите соответствующий указатель в таблицу и добавьте его в текущий результат.

Конечно, я не уверен, насколько хорошо это будет работать, но это мысль.

Answer 4

Алгоритм довольно прост. Языковая независимость будет:

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') или любых других исключительных условиях.

Answer 5

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

Если приемлемо решение на 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;
}

Answer 6

Насколько точно вы должны быть?

Если вы ищете совершенства, то умножение и сложение - это действительно ваш единственный выход. И я был бы очень удивлен, если это самая медленная часть вашего приложения.

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

Пример 1: 1234, ближайшая степень 2 - 1024. Пример 2: 98765, ближайший - 65536

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

Пример 3: 98765 имеет 5 цифр, ближайшая степень от 2 до 10000 равна 8192 (2 ^ 13), поэтому результат равен 9 << 13 </p>

Answer 7

• Начните с текущего счета 0.
• Для каждого символа в строке (чтение слева направо)
  • Умножьте счет на базу.
  • Преобразование символа в значение типа int (от 0 до основания)
  • Добавить символьное значение к счетчику.