我如何将表示为数字数组的数字从 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

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

Answer 1

基数 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.

所以二进制数字的最后一部分将是：

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

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

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。我会把它留作练习。

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

How would I convert a number represented as an array of digits from base-2^k to binary?

algorithm

binary

decimal