int - varints 如何占用更少的空间？

Question

我正在尝试了解 varints，而我发现的最好的东西是这个Google Protocol Buffers spec。

在他们的示例中，他们表明这个数字1010 1100 0000 0010在使用 varints 编码时300与44034.

通常数字 300 占用两个字节 ( 1 0010 1100)，但他们的示例中的 300 也是如此。varints 如何实际上比普通 int 占用更少的字节？

标签： intintegerprotocol-buffersvarint

Answer 1

300 通常占用两个字节，如果您使用 2 字节的固定格式来表示它。如果您使用 4 字节或 8 字节格式，则需要 4 字节或 8 字节。如果您使用的是 1 字节格式，则根本无法表示 300，除非您使用的是非常奇怪的编码。

如果您想使用可变长度编码，那么标准 2 的补码表示是不够的，因为它没有长度信息。你不会知道数字停在哪里。您可以单独对长度进行编码，但这会增加您的空间需求......或者您可以使用类似 protobuf varint 表示的东西，它可以在 2 个字节中表示 300，并包含一个信号，表明该数字在该点已完成。

（或者您可以使用许多其他编码中的一种。Protobuf 变体并非明确优于其他表示，即使在使用的空间方面也是如此。总有权衡。）