从十进制字符串为二进制重新presentation转换一个非常大的数字？ [英] Convert a very large number from decimal string to binary representation?

问题描述

我有一个非常大的数字，千位十进制数字的数量级，而我将其转换为二进制的重新presentation。这些号码存储为字符串。

I have a very big number, on the order of a thousand decimal digits, and I have to convert this to its binary representation. The numbers are stored as strings.

由于很少有语言有一个基本的数据类型来处理这个数字大，我看不出有什么简单的方法来变成一个整数值本作，我可以将其转换。

Since few languages have a basic data type to handle numbers this big, I see no easy way to turn this into an integral value for which I could convert it.

可能有人请帮助我在这里？什么将是一个可行的方法这样做？

Could someone please help me out here? What would be a viable approach for doing this?

推荐答案

如果这是一个真正的问题，有很多BIGNUM图书馆在那里协助，如的 MPIR 库。

If this is a genuine problem, there are plenty of BigNum libraries out there to assist, such as the MPIR library.

如果这就是你的有事不能的使用第三方库，它还是比较容易的。其实你不的需要的这种复杂BIGNUM库，你只需要一个操作：除2

If it's something where you can't use a third-party library, it's still relatively easy. You don't actually need a complex BigNum library for this, you only need one operation: divide by two.

下面是你如何做到这一点。开始用二进制数字空堆栈。然后循环，直到数为0（是的，这仍然是一个字符串）。如果数字的最后一位数字为奇数，推1上堆叠，否则推0。然后除以二的数量，并重新启动循环

Here's how you do it. Start with an empty stack of binary digits. Then loop until the number is "0" (yes, that's still a string). If the last digit of the number is odd, push 1 on to the stack, otherwise push 0. Then divide the number by two and restart the loop.

在循环结束（编号为0），弹出数字从堆栈一次一个，并打印出来。你去那里。

Once the loop is finished (number is "0"), pop the digits off the stack one at a time and print them. There you go.

哦，对了，除以2，得到的是的难题一个比较重要的一块： - ）

Oh, yeah, the divide-by-two, that is a rather important piece of the puzzle :-)

让我们先从12345。这里是你遵循的流程，在伪code。

Let's start with "12345". Here's the process you follow, in pseudo-code.

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 (and truncate if necessary).
Remove leading zero if necessary (if it starts with 0 but is not just 0).

这可以通过一次处理的实际串一个字符来完成。

This can be done by processing the actual string one character at a time.

• 开始以 1 （从 12345 ），添加剂 0 ，数量为奇数，所以next_additive是 5 。鸿沟 1 按 2 并添加 0 的添加剂，你GET 0 ： 02345

• Starting with 1 (from 12345), additive is 0, number is odd, so next_additive is 5. Divide 1 by 2 and add additive of 0, you get 0: 02345.

下一个数字 2 ，添加剂 5 ，数量为偶数，所以next_additive是 0 。鸿沟 2 按 2 并添加 5 的添加剂，你GET 6 ： 06345

Next digit 2, additive is 5, number is even, so next_additive is 0. Divide 2 by 2 and add additive of 5, you get 6: 06345.

下一个数字 3 ，添加剂 0 ，数量为奇数，所以next_additive是 5 。鸿沟 3 按 2 并添加 0 的添加剂，你GET 1 ： 06145

Next digit 3, additive is 0, number is odd, so next_additive is 5. Divide 3 by 2 and add additive of 0, you get 1: 06145.

下一个数字 4 ，添加剂 5 ，数量为偶数，所以next_additive是 0 。鸿沟 4 按 2 并添加 5 的添加剂，你GET 7 ： 06175

Next digit 4, additive is 5, number is even, so next_additive is 0. Divide 4 by 2 and add additive of 5, you get 7: 06175.

下一个数字 5 ，添加剂 0 ，数量为奇数，所以next_additive是 5 。鸿沟 5 按 2 并添加 0 的添加剂，你GET 2 ： 06172

Next digit 5, additive is 0, number is odd, so next_additive is 5. Divide 5 by 2 and add additive of 0, you get 2: 06172.

剥去前导零： 6172 。忽略接下来的添加剂，因为你截断的结果。

Strip off leading zeros: 6172. Ignore the next additive since you're truncating the result.

和你有它：二分之一万二千三百四十五= 6172

举例来说，这里是一个Python的方法来实现这个算法如下。首先，用于检查字符串个数为奇数的支持例程（请记住，这不是的意味着的Python化code，它只是为了显示它如何能够做到 - 有几乎肯定更好的方法来做到这一点在Python但不一定会很好地映射到另一种语言）：

By way of example, here's a Python approach to implementing this algorithm as follows. First the support routine for checking if a string-number is odd (keep in mind this isn't meant to be Pythonic code, it's just to show how it could be done - there's almost certainly better ways to do this in Python but that won't necessarily map well to another language):

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

然后分割字符串数由两个另一支持程序：

Then another support routine for dividing a string-number by two:

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

和，最后，实际code键从十进制字符串进行二进制串：

And, finally, the actual code to make a binary string from the decimal string:

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

请注意，如果你想真正使用它来填充实位（而不是让比特串），这是一个简单的事情，改变发生的事情如果声明。

Note that if you wanted to actually use this to populate real bits (rather than make a string of bits), it's a simple matter to change what happens in the if statement.

如前所述，它可能不是的最的效率或美丽的Python code，你能想出，但它只是意在显示过程中，没有出现一些精心设计的生产就绪件的code。输出是（下面一些附加的东西，以显示这是怎么回事）：

As stated, it's probably not the most efficient or beautiful Python code you could come up with but it's simply meant to show the process, not be some well-engineered production-ready piece of code. The output is (with some added stuff below to show what's going on):

12345
11000000111001
||      |||  |
||      |||  +-     1
||      ||+----     8
||      |+-----    16
||      +------    32
|+-------------  4096
+--------------  8192
                =====
                12345

这篇关于从十进制字符串为二进制重新presentation转换一个非常大的数字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！