algorithm - 我如何将表示为数字数组的数字从 base-2^k 转换为二进制？

Question

我有一个算法可以模拟手动将二进制数转换为十进制数。我的意思是每个数字都表示为数字数组(从最低到最高)，而不是使用语言的 int 或 bigint 类型。

例如，以 10 进制表示的 42 将表示为 [2, 4]，而以 2 进制表示的 10111 将表示为 [1, 1, 1, 0, 1]。

这是用 Python 编写的。

def double(decimal):
    result = []
    carry = 0
    for i in range(len(decimal)):
        result.append((2 * decimal[i] + carry) % 10)
        carry = floor((2 * decimal[i] + carry) / 10)
    if carry != 0:
        result.append(carry)
    return result

def to_decimal(binary):
    decimal = []
    for i in reversed(range(len(binary))):
        decimal = double(decimal)
        if binary[i]:
            if decimal == []:
                decimal = [1]
            else:
                decimal[0] += 1
    return decimal

这是几个学期前我在算法课上完成的作业的一部分，他在他的笔记中向我们提出了挑战，声称我们应该能够从这个算法中推导出一个新的算法，该算法可以将数字从base-2^k 到二进制。我今天把它挖出来，它一直困扰着我(阅读:让我觉得真的很生疏)，所以我希望有人能够解释我将如何编写一个基于 to_binary(number, k) 函数关于这个算法。

Answer 1

Base 2^k 有数字 0, 1, ..., 2^k - 1。

例如，在 2^4 = 16 中，我们有数字 0, 1, 2, ..., 10, 11, 12, 13, 14, 15。为方便起见，我们使用字母表示较大的数字:0、1、...、A、B、C、D、E、F。

假设您要将 AB 转换为二进制。简单的事情是先将其转换为十进制，因为我们知道如何将十进制转换为二进制:

AB = B*16^0 + A*16^1 
   = 11*16^0 + 10*16^1
   = 171

如果将 171 转换为二进制，您将得到:

10101011

现在，有没有我们可以使用的捷径，这样我们就不用以 10 为基数了？有。

让我们在这部分停下来:

AB = B*16^0 + A*16^1 
   = 11*16^0 + 10*16^1

并回想一下将十进制转换为二进制需要做些什么:将整数除以 2，记下余数，最后以相反的顺序写下余数:

number after integer division by 2 | remainder after integer division by 2
--------------------------------------------------------------------------
                                 5 | 1
                                 2 | 0
                                 1 | 1
                                 0 |

                  => 5 = reverse(101) = 101 in binary

让我们将其应用到这部分:

11*16^0 + 10*16^1 

首先，对于第一个4(因为16^1 = 2^4)除法，除以2的余数将仅取决于 11，因为 16 % 2 == 0。

11 | 1
5  | 1
2  | 0
1  | 1
0  |

所以我们的二进制数字的最后一部分将是:

1011

当我们完成此操作时，我们将摆脱 16^1，因为到目前为止我们已经完成了 4 的除法。所以现在我们只依赖于10:

10 | 0
 5 | 1
 2 | 0
 1 | 1
 0 |

所以我们的最终结果将是:

10101011

这就是我们用经典方法得到的结果!

正如我们所注意到的，我们只需要将数字单独转换为二进制，因为它们将单独和顺序地影响结果:

A = 10 = 1010
B = 11 = 1011

=> AB in binary = 10101011

对于您的基 2^k，执行相同操作:将每个单独的数字转换为二进制，从最高位到最低位，然后按顺序连接结果。

示例实现:

def to_binary(number, k):
    result = []
    for x in number:
        # convert x to binary
        binary_x = []
        t = x
        while t != 0:
            binary_x.append(t % 2)
            t //= 2
        result.extend(binary_x[::-1])

    return result

#10 and 11 are digits here, so this is like AB.
print(to_binary([10, 11], 2**4))
print(to_binary([101, 51, 89], 2**7))

打印:

[1, 0, 1, 0, 1, 0, 1, 1]
[1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1]

注意:上面的代码其实有一个bug。例如，基数 2**7 中的 2 将以二进制形式转换为 10。但是基数 2**7 中的数字应该有 7 位，因此您需要将它填充到那么多位:0000010。我将把它留作练习。