将十进制数字转换为二进制表示形式的非常大的数字？

Question

我有一个非常大的数字,大约一千位十进制数字,我必须将其转换为二进制表示.数字存储为字符串.

由于很少有语言具有基本数据类型来处理这么大的数字,我认为没有简单的方法可以将其转换为可以转换它的整数值.

有人可以帮帮我吗？这样做的可行方法是什么？

Answer 1

如果这是一个真正的问题,有很多BIGNUM库在那里协助,如MPIR库.

如果它不能使用第三方库,那么它仍然相对容易.你实际上并不需要一个复杂的BigNum库,你只需要一个操作:除以2.

这是你如何做到的.从一堆空二进制数字开始.然后循环直到数字为"0"(是的,那仍然是一个字符串).如果数字的最后一位是奇数,则将1按到堆栈,否则按0.然后将数字除以2并重新启动循环.

循环结束后(数字为"0"),一次一个地从堆栈中弹出数字并打印出来.你去吧

哦,是的,除以二,这是一个相当重要的难题:-)

让我们从"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(从12345)开始,加法是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

然后是另一个将字符串数除以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

最后,一些实际代码从十进制字符串生成二进制字符串:

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子句中发生的事情是一件简单的事情.

如上所述,它可能不是你能想到的最有效或最漂亮的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