Преобразовать очень большое число из десятичной строки в двоичное представление?

Question

У меня есть очень большое число, порядка тысячи десятичных цифр, и я должен преобразовать его в двоичное представление. Числа хранятся в виде строк.

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

Может ли кто-нибудь помочь мне здесь? Каков был бы жизнеспособный подход для этого?

Answer 1

Если это настоящая проблема, существует множество библиотек BigNum, таких как библиотека MPIR.

Если вы не можете использовать стороннюю библиотеку, это все равно относительно просто. Для этого вам не нужна сложная библиотека BigNum, вам нужна только одна операция: разделите на две.

Вот как ты это делаешь. Начните с пустого стека двоичных цифр. Затем выполните цикл, пока число не станет равным "0" (да, это все еще строка). Если последняя цифра числа нечетная, нажмите 1 на стеке, в противном случае нажмите 0. Затем разделите число на два и перезапустите цикл.

Когда цикл завершен (число равно "0"), вытолкните цифры из стека по одной за раз и напечатайте их. Вот и ты.

---

О, да, деление на два, это довольно важная часть головоломки:-)

Начнем с "12345". Вот процесс, которому вы следуете, в псевдокоде.

Set next_additive to 0.
For every digit in number (starting at the left):
    Set additive to next_additive.
    If the digit is odd, set next_additive to 5, else set it to 0.
    Divide the digit by two (truncating) then add additive.
Remove leading zero if necessary (if it starts with 0 but is not just 0).

Это может быть сделано путем обработки фактической строки по одному символу за раз.

• Начиная с 1 (от 12345), добавка 0, число нечетное, поэтому next_additive 5, Делить 1 от 2 и добавить добавку 0, ты получаешь 0: 02345,

• Следующая цифра 2, добавка 5 число четное, поэтому next_additive 0, Делить 2 от 2 и добавить добавку 5, ты получаешь 6: 06345,

• Следующая цифра 3, добавка 0, число нечетное, поэтому next_additive 5, Делить 3 от 2 и добавить добавку 0, ты получаешь 1: 06145,

• Следующая цифра 4, добавка 5 число четное, поэтому next_additive 0, Делить 4 от 2 и добавить добавку 5, ты получаешь 7: 06175,

• Следующая цифра 5, добавка 0, число нечетное, поэтому next_additive 5, Делить 5 от 2 и добавить добавку 0, ты получаешь 2: 06172,

• Снять ведущие нули: 6172, Игнорируйте следующую добавку, так как вы усекаете результат.

И вот оно у вас есть: 12345 / 2 = 6172,

---

В качестве примера, вот Python подход к реализации этого алгоритма следующим образом. Сначала подпрограмма поддержки для проверки, является ли строковое число нечетным (имейте в виду, что это не Python-код, это просто демонстрация того, как это можно сделать - почти наверняка есть лучшие способы сделать это в Python, но это выиграло не обязательно карта хорошо на другой язык):

def oddsToOne(s):
    if s.endswith('1'): return 1
    if s.endswith('3'): return 1
    if s.endswith('5'): return 1
    if s.endswith('7'): return 1
    if s.endswith('9'): return 1
    return 0

Затем еще одна подпрограмма поддержки для деления строкового числа на два:

def divByTwo(s):
    new_s = ''
    add = 0

    for ch in s:
        new_dgt = (ord(ch) - ord('0')) // 2 + add
        new_s = '%s%d' % (new_s, new_dgt)
        add = oddsToOne(ch) * 5

    if new_s != '0' and new_s.startswith('0'):
        new_s = new_s[1:]

    return new_s

И, наконец, некоторый фактический код для создания двоичной строки из десятичной строки:

num = '12345'

if num == '0':
    stack = '0'
else:
    stack = ''
    while num != '0':
        stack = '%d%s'%(oddsToOne(num), stack)
        num = divByTwo (num)

print(stack)

Обратите внимание, что если вы хотите использовать это для заполнения реальных битов (а не для создания строки битов), то просто изменить то, что происходит в if а также else статьи.

Как уже говорилось, это, вероятно, не самый эффективный или красивый код Python, который вы могли бы придумать, но он просто предназначен для демонстрации процесса, а не для какого-то хорошо спроектированного, готового к использованию фрагмента кода. Вывод (с некоторыми добавленными вещами ниже, чтобы показать, что происходит):

12345
11000000111001
||      |||  |
||      |||  +-     1
||      ||+----     8
||      |+-----    16
||      +------    32
|+-------------  4096
+--------------  8192
                =====
                12345

---

Поскольку это работает со строковым представлением чисел, не существует произвольного числового ограничения, такого как размер 64-разрядного целого числа. Некоторые примеры значений (немного переформатированы в 32-значные блоки для удобства чтения):

123456781234567812345678
=> 11010001001001001101100000011011
   01110110001110110010110110101111
   0111101001110

99999999999999999999999999999999
99999999999999999999999999999999
99999999999999999999999999999999
9999
=> 10010010010011010110100100101100
   10100110000110111110011101011000
   01011001001111000010011000100110
   01110000010111111001110001010110
   01110010000001000111000100001000
   11010011111001010101010110010010
   00011000010001010100000101110100
   01111000011111111111111111111111
   11111111111111111111111111111111
   11111111111111111111111111111111
   1111111111111