13

こんにちは、

言語の最大の整数型のビットよりも多くの文字を含む2進文字列を10進文字列に変換するにはどうすればよいですか？言い換えれば、あなたが文字列を持っていると仮定します

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 の累乗ではないため、2 進数表現の任意の場所の数字は、10 進数表現の最下位桁に影響を与える可能性があります。ビット文字列を変換するには、10 進表現全体を格納する必要があります。

お使いの言語用の長い 10 進データ クラス/ライブラリが見つからない場合は、自分で構築できます。難しくありません。リストなどとして十分な数の 10 進数を格納し、計算を行うだけです。このタスクに必要なのは追加だけなので、実装は非常に簡単です。

于 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に対応し、インデックス1のアイテムは10に対応します。

于 2011-03-09T14:29:27.560 に答える
2

GMPのような任意精度の数値 (bignum) ライブラリを使用します。

GMP には「gmp_scanf」関数があり、まさにあなたが求めていることを実行します。

于 2011-03-09T14:23:36.660 に答える
0

自由に使える任意精度の数学パッケージは持っていないが、基本的な文字列操作ルーチンのセットがあると仮定すると、次のことができます。

2 の累乗のリストを作成し、文字列の「1」ビットごとに適切な 2 の累乗を追加することにより、一度に 1 ビットずつ逆の順序でバイナリ文字列を分解します。

これを行うために必要な唯一の任意精度の算術関数は加算であり、これはロングハンド算術を使用して実装するのがかなり簡単です。

と呼ばれる任意の算術加算関数を実装したとします。10 ADD進数を含む 2 つの文字列を入力として受け取り、10 進数の合計を文字列として返します。何かのようなもの：

  SumString = ADD(DecimalString1, DecimalString2)

SumStringDecimalString1との合計を表す 10 進数の文字列です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 ベース (0 ベースではなく) であることを前提としています。

ステップ 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): 2 つの文字列の連結を返します
  • substr(String, start, length): string の start から length 文字の部分文字列を返します (1 ベース)
  • CtoI(String): 指定された文字の 10 進整数値を返します (例: '1' = 1、'2' = 2、...)
  • ItoC(Integer): 整数の 10 進文字表現を返します (例: 1 = '1'、2 = '2'、...)
  • コピー（カウント、文字列）：文字列の連結されたコピーの数を返します
于 2011-03-09T17:31:01.290 に答える