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

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

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

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

 Junuxx13 июн. 2012 г., 02:56
Подумайте об отношениях между 10 ^ x и 2 ^ x на мгновение ...
 frodo13 июн. 2012 г., 11:34
@StephenC. Я возвращаю количество бит (bin [bits ++]). это просто то, что я использовал позже. bin [] содержит двоичное число. Вы можете попробовать этот код, он отлично работает.
 frodo13 июн. 2012 г., 03:57
@mattegod. ну извини, если ты так чувствуешь. Я все равно понял. Спасибо за всю большую помощь. :Пcodeint string_to_binary (int bin [], char s []) {// int len = strlen (s); int res = 0; int bits = 0; целые числа; for (цифры = 0; s [цифры]; цифры ++) s [цифры] - = '0'; int firstdigit = 0; Int остаются; int i; while (firstdigit & lt; digits) {for (i = firstdigit, остаются = 0; i & lt; цифры; i ++) {остаются = 10 * остаются + s [i]; s [i] = остается / 2; оставайся% = 2; // printf (& quot;% d & quot; s [i]); } bin [bits ++] = остаются; while ((firstdigit & lt; digits) и! s [firstdigit]) firstdigit ++; } возвращаемые биты; }
 Stephen C13 июн. 2012 г., 09:44
@frodo - это не похоже на решение проблемыthat you stated, Для начала он возвращаетint ... и это никак не10^1000 вписывается вint.
 nhahtdh13 июн. 2012 г., 03:00
Я не уверен, есть ли какой-нибудь простой способ. В исходном коде Java BigInteger он преобразует несколько цифр в целое число и «накапливает» перевести его в двоичное представление, выполнив умножение и сложение с большим целым числом (т. е. прежде чем выполнять преобразование строки, нужно записать операции умножения + сложения с большим целым числом).

Ответы на вопрос(1)

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

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

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

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

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

Давайте начнем с "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).

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

Starting with 1 (from 12345), additive is 0, number is odd, so next_additive is 5. Divide 1 by 2 and add additive of 0, you get 0: 02345.

Next digit 2, additive is 5, number is even, so next_additive is 0. Divide 2 by 2 and add additive of 5, you get 6: 06345.

Next digit 3, additive is 0, number is odd, so next_additive is 5. Divide 3 by 2 and add additive of 0, you get 1: 06145.

Next digit 4, additive is 5, number is even, so next_additive is 0. Divide 4 by 2 and add additive of 5, you get 7: 06175.

Next digit 5, additive is 0, number is odd, so next_additive is 5. Divide 5 by 2 and add additive of 0, you get 2: 06172.

Strip off leading zeros: 6172. Ignore the next additive since you're truncating the result.

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

В качестве примера, здесь Python-подход к реализации этого алгоритма заключается в следующем. Сначала подпрограмма поддержки для проверки, является ли число строки нечетным (имейте в виду, что это не такmeant быть 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 статьи.

Как уже говорилось, это, вероятно, неmost эффективный или красивый код 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
 12 апр. 2014 г., 13:30
@paxdiablo, это отличный ответ. Спасибо.
 08 мар. 2016 г., 05:11
@derek,all в этом ответе выполняются операции над строками (см. мой текстyes, that's still a string) так что естьno произвольный числовой предел на значения. Единственным ограничением является место для хранения. Фактически, я покажу вывод для вашего точного случая (и гораздо большего).
 21 мар. 2014 г., 10:36
У вас есть идея преобразовать двоичный файл обратно в десятичную строку?
 07 мар. 2016 г., 18:04
это не будет работать, если входная десятичная строка очень велика. Поскольку, если десятичная строка очень большая, она не может быть представлена в виде числа и, следовательно, ее нельзя разделить на 2. попробуйте это: & quot; 123456781234567812345678 & quot ;.
 08 мар. 2016 г., 05:35
Вы правы. Я не заметил, что вы работаете на струнах. Хорошее решение!

Ваш ответ на вопрос