5

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

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

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

4

1 回答 1

47

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

如果是不能使用第三方库的东西，还是比较容易的。你实际上并不需要一个复杂的 BigNum 库，你只需要一个操作：除以二。

这是你如何做到的。从一个空的二进制数字堆栈开始。然后循环直到数字为“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(from 12345) 开始，additive 是0，number 是奇数，所以 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

然后是另一个将字符串数除以二的支持例程：

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)

请注意，如果您想实际使用它来填充真实位（而不是制作一串位），那么更改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 回答