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

Question

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

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

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

Answer 1

如果这是一个真正的问题，那么有很多 BigNum 库可以提供帮助，例如 MPIR 库。

如果是无法使用第三方库的东西，它仍然相对容易。您实际上不需要复杂的 BigNum 库，您只需要一个操作：除以二。

这是你如何做到的。从一堆空的二进制数字开始。然后循环直到数字为"0"（是的，这仍然是一个字符串）。如果数字的最后一位是奇数，则按 1 到堆栈，否则按 0。然后将数字除以二并重新开始循环。

循环完成后（数字为"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 方法，如下所示。首先是检查字符串数字是否为奇数的支持例程（请记住，这并不意味着 Pythonic 代码，它只是为了展示如何做到这一点 - 几乎可以肯定有更好的方法可以在 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