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