Двоичная строка в десятичную строку

Question

Добрый день,

Как бы вы преобразовали в десятичную строку двоичную строку, содержащую больше символов, чем бит, в самом большом целочисленном типе языка?Другими словами, если у вас есть строка

111001101001110100100(...)1001001111011100100

и что вы не можете сначала преобразовать ее в целое число, как бы вы записали ее в основание 10?

Спасибовам очень нравится.

Answer 1

Вы можете использовать алгоритм как:

// X is the input
while ( X != "0" )
  compute X' and R such that X = 10 * X' + R  (Euclidean division, see below)
  output R    // least significant decimal digit first
  X = X'

Евклидово деление X на 10 вычисляется так:

R = 0  // remainder in 0..9
X' = ""
for (b in bits of X)  // msb to lsb
  R = 2*R + b
  if R >= 10
    X' += "1"
    R -= 10
  else
    X' += "0"

Remove leading "0" from X'
The remainder is R in 0..9

Answer 2

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

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

Answer 3

Напишите свою собственную арифметику в базе 10. Требуется только сложение.Пример реализации в Python:

from math import log, ceil

def add(a, b):
    """Add b to a in decimal representation."""
    carry = 0
    for i in range(len(b)):
        carry, a[i] = divmod(a[i] + b[i] + carry, 10)
    while carry:
        i += 1
        carry, a[i] = divmod(a[i] + carry, 10)

# an example string
s = bin(3 ** 120)[2:]

# reserve enough decimal digits
res = [0] * int(ceil(len(s) * log(2) / log(10)))

# convert
for c in s:
    add(res, res)
    if c == "1":
        add(res, [1])

#print output
print str.join("", map(str, reversed(res)))

При этом используются списки промежуточных чисел для представления чисел в базе 10. Пункты списка соответствуют цифрам номера базовой 10.Элемент с индексом 0 соответствует единице, элемент с индексом 1 - десятками и т. Д.

Answer 4

Я бы использовал библиотеку чисел произвольной точности (bignum), например GMP .

GMP имеет функцию " gmp_scanf ", которая выполняет именно то, что вы просите.

Answer 5

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

Построить список степеней 2, а затем деконструировать двоичную строку в обратном порядке. упорядочивайте по одному биту за раз, добавляя соответствующую степень 2 для каждого бита '1' в строке.

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

Предположим, вы реализовали произвольную арифметическую функцию добавления, которая называется: ADD принимает 2 строки, содержащие десятичные числа, в качестве входных данных и возвращает десятичную сумму как строка Что-то вроде:

  SumString = ADD(DecimalString1, DecimalString2)

SumString - это строка десятичных цифр, представляющая сумму DecimalString1 и DecimalString2.

Шаг 1. Составьте список из 2-х степеней следующим образом:

  BitString is string           /* String of '1' and '0' values... */
  BitString = '111001101001110100100(...)1001001111011100100' /* or whatever... */

  PowerOf2 is array of string  /* Array of strings containing powers of 2 */
  PowerOf2[1] = '1'            /* 2**0 to get things started... */
  /* Build as many powers of 2 as there are 'bits' in the input string */   
  for i from 2 to length(BitString) by +1  
    PowerOf2[i] = ADD(PowerOf2[i-1], PowerOf2[i-1])  
    end 

Примечание. Выше предполагается, что массивы / строки основаны на 1 (в отличие от нуля).

Шаг 2: Деконструируйте BitString, накапливая сумму по ходу:

  DecimalValue is string        /* Decimal value of BitString */
  BitString is string           /* Your input set of bits as a string... */
  ReverseBitString is string    /* Reversed input */

  DecimalValue = ''             /* Result */  
  BitString = '111001101001110100100(...)1001001111011100100' /* or whatever... */  
  ReverseBitString = reverse(BitString) /* Reverse so we process lsb to msb */  

  for i from 1 to length(ReverseBitString) by +1  
     if substr(ReverseBitString, i, 1) == '1' then  /* Bit at position i */  
        DecimalValue = ADD(DecimalValue, PowerOf2[i])  
        end   
     end    

  if DecimalValue = '' then DecimalValue = '0' /* bit string was all zero */   
  Display DecimalValue /* This is the result */  

Как построить функцию произвольной точности ADD? Это выглядит примерно так:

  function ADD (DecVal1 is string, DecVal2 is string) return string  
     SumVal is string   
     Rev1 is string  
     Rev2 is string      
     DigitSum is integer
     CarryDigit is integer

     SumVal = ''               /* Result so far... */
     Rev1 = reverse(DecVal1)   /* Reverse digit order */
     Rev2 = reverse(DecVal2)   /* Reverse digit order */

     /* Pad shorter reversed sting with trailing zeros... */
     if length(Rev1) > length(Rev2) then
        Rev2 = concat(Rev2, copies(length(Rev1) - length(Rev2), '0')
        end
     else
        Rev1 = concat(Rev1, copies(length(Rev2) - length(Rev1), '0')
        end

     /* Sum by digit position, least to most significant */
     CarryDigit = 0    
     for i from 1 to length(Rev1) by + 1
        DigitSum = CtoI(substr(Rev1, i, 1)) + CtoI(substr(Rev2, i, 1)) + CarryDigit
        if DigitSum > 9 then
           DigitSum = DigitSum - 10
           CarryDigit = 1
           end
        else
           CarryDigit = 0
           end 

        SumVal = concat(ItoC(DigitSum), SumVal)
        end

      if CarryDigit > 0 then
        SumVal = concat(ItoC(CarryDigit), SumVal)
        end

      return SumVal  

Предполагаемые встроенные строковые функции:

• reverse (String): возвращает строку в обратном порядке
• length (String): Возвращает длину данной строки
• concat (String, String): возвращает объединение двух строк
• substr (String, start, length): возвращает подстроку строки из начала для символов длины (на основе 1)
• CtoI (String): возвращает десятичное целочисленное значение заданного символа (например, '1' = 1, '2' = 2, ...)
• ItoC (Integer): возвращает десятичное представление целого числа (например, 1 = '1', 2 = '2', ...)
• копий (количество, строка): возвращает количество конкатинированных копий строки