5

私は1000桁の非常に大きな数を持っており、これを2進表現に変換する必要があります。番号は文字列として保存されます。

これほど大きな数値を処理するための基本的なデータ型を持つ言語はほとんどないため、これを変換できる整数値に変換する簡単な方法はありません。

誰かがここで私を助けてくれませんか？これを行うための実行可能なアプローチは何でしょうか？

4

1 に答える 1

47

これが本当の問題である場合は、MPIR ライブラリなど、役立つ BigNum ライブラリがたくさんあります。

サードパーティのライブラリを使用できない場合でも、比較的簡単です。これには実際には複雑な BigNum ライブラリは必要ありません。必要な操作は 2 で割るだけです。

方法は次のとおりです。2 進数の空のスタックから始めます。次に、数値が「0」になるまでループします (はい、それはまだ文字列です)。数字の最後の桁が奇数の場合は 1 をスタックにプッシュし、そうでない場合は 0 をプッシュします。次に、数字を 2 で割り、ループを再開します。

ループが終了したら (番号は「0」)、スタックから数字を 1 つずつポップして出力します。ほらね。

ああ、そうです、2 で割ることは、パズルのかなり重要なピースです :-)

「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 文字ずつ処理することで実行できます。

  • 1(from ) から始めて12345、additive は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

次に、string-number を 2 で除算するための別のサポート ルーチン:

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

最後に、10 進文字列からバイナリ文字列を作成する実際のコードを次に示します。

num = '12345'

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

print(stack)

実際にこれを使用して (ビットの文字列を作成するのではなく) 実際のビットを設定する場合は、ifandelse句で何が起こるかを変更するのは簡単なことです。

述べたように、これはおそらく最も効率的で美しい 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
于 2012-06-13T01:18:39.320 に答える