13

下午好，

您将如何将一个二进制字符串转换为十进制字符串，该二进制字符串的字符数比语言最大整数类型中的位数多？换句话说，假设你有字符串

111001101001110100100(...)1001001111011100100

并且您不能先将其转换为整数，您将如何以 10 为基数编写它？

非常感谢。

4

5 回答 5

14

您可以使用如下算法：

// 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
于 2011-03-09T14:29:20.410 回答
4

10 不是 2 的幂，因此二进制表示中任何位置的数字都可能影响十进制表示中的最低有效位。您必须存储整个十进制表示来转换位串。

如果找不到适合自己语言的长十进制数据类/库，可以自己构建，不难。只需存储足够的十进制数字，例如作为列表，然后进行数学计算。你只需要添加这个任务，所以它很容易实现。

于 2011-03-09T14:24:34.503 回答
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 处的项目对应于十位，依此类推。

于 2011-03-09T14:29:27.560 回答
2

我会使用任意精度的数字（bignum）库，比如GMP。

GMP 有一个“ gmp_scanf ”功能，可以满足您的要求。

于 2011-03-09T14:23:36.660 回答
0

假设您没有任意精度的数学包可供使用，但您确实有一组基本的字符串操作例程，您可以执行以下操作：

构造一个 2 的幂列表，然后通过为字符串中的每个“1”位添加适当的 2 幂，以相反的顺序一次一位地解构二进制字符串。

您需要执行此操作的唯一任意精度算术函数是加法，并且使用长手算术很容易实现。

假设您确实实现了一个名为的任意算术加法函数： ADD将 2 个包含十进制数字的字符串作为输入并将十进制总和作为字符串返回。就像是：

  SumString = ADD(DecimalString1, DecimalString2)

SumString是一串十进制数字，表示 和 的DecimalString1和DecimalString2。

Step1：构造一个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)：从 start 开始返回 string 的子字符串，用于 length 个字符（从 1 开始）
  • CtoI(String)：返回给定字符的十进制整数值（例如，'1' = 1，'2' = 2，...）
  • ItoC(Integer)：返回整数的十进制字符表示（例如 1 = '1', 2 = '2', ...）
  • 副本（计数，字符串）：返回计数连接的字符串副本
于 2011-03-09T17:31:01.290 回答