仅编码无符号整数时的base64字符串长度计算

Question

我正在尝试估计我可以使用 5 个 base64 字符、6 个字符等编码的无符号整数。

通过编程方法我发现我可以编码

2^28 - 1 = 268,435,455

有 6 个字符并且

2^35 - 1 = 34,359,738,368

有 7 个字符。

（-1 因为我从 uint 1 开始）

虽然我很难概括这一点，因为我假设它从 2^8 = 256 开始，但我不明白我是如何在 28 和 35 结束的。

这是我在 Go 中的实现

func Shorten(num uint64) string {
    buf := make([]byte, binary.MaxVarintLen64)
    n := binary.PutUvarint(buf, num)
    b := buf[:n]
    encoded := base64.URLEncoding.EncodeToString(b)
    return strings.Replace(encoded, "=", "", -1)
}

还有

0 -> AA
128 -> gAE
16384 -> gIAB
2097152 -> gICAAQ
268435456 -> gICAgAE

看起来它以 7 个增量上升：2^7、2^14、2^21 等，但为什么是 7？

Answer 1

一个字节是 8 位，因此有 256 个可能的值。 Base 64 使用 64 个不同的字符进行编码，因此使用 6 位。那么 6 位可以容纳多少个 8 位对象？如果四舍五入则为 0，否则为 3/4。当您开始谈论对整数进行编码时，您的数字似乎没有意义。您是在谈论用 ascii 编写的整数吗？有 6 个 base64 字符，你有 36 位可以玩，所以如果你谈论二进制 32 位无符号整数，你可以一次编码一个，但你可以编码任何你想要的 2**32 种不同的可能性，然后4个浪费位。使用 ascii 你会有 4 个字符，所以它有 10000 种不同的可能性（0 到 9999）。

您得到了意想不到的结果，因为您使用的是未编码为常规二进制整数的 go varint。一些 ipython 输出给你：

In [22]: base64.b64encode((128).to_bytes(1,'little'))                                                                                          
Out[22]: b'gA=='

因为 128 可以编码为单个 8 位字节，所以它只有 2 个字符并带有一些填充。看看这个：

In [3]: base64.b64decode('gAE=')                                                                                                               
Out[3]: b'\x80\x01'

In [4]: int.from_bytes(_,'little')                                                                                                             
Out[4]: 384

所以正如您所看到的，PutUVarint 不仅仅是编码一个可变长度的整数，它还在编码一个可变整数，即它的编码方式可以在事先不知道它的大小的情况下进行解码。如果您查看 source code for the varint go module，它描述了这个过程。 Go 使用每个字节的 7 位来保存实际的整数二进制数据，最高有效位是一个标志，表示是否还有更多数据尚未到来。 128 只是一个字节集的最高有效位。所以基本上你根据完成这项任务的方式进行了两次编码。如果您有一个给定的整数将其编码为 var int，则您需要整数使用 *8/7 来存储该值的字节数，然后您对该结果进行 base64 编码，因此您需要该值 *8/6 来存储它。根据你对 base64 的处理方式，你可能可以确定你正在玩多少字节而无需求助于 go varints 然后计算将只是 8/6 转换（这是 4/3 我只是将它留在位中以更接近地匹配 varint 过程。）

仅编码无符号整数时的base64字符串长度计算

base64 string length calculation when encoding unsigned integers only

python

base64

encoding

go