algorithm - What is the minimum of bytes to encode a number?

Question

I need to encode a number in range from 0 to 7^20 (integer). I want to use the minimum of bytes to encode a such number. So what is the minimum of bytes to do that? please help me. Thank you so much

Answer 1

您需要从 0 编码到 7 ²⁰，这意味着总共有 7 ²⁰ + 1 个值。如果没有关于输入的任何信息，您能做的最好的事情是 ⌈log ₂ (7 ²⁰ + 1)⌉ = 每个数字 57 位。

您可以为每个数字提供 8 个字节，这也很容易解码。但是每个数字浪费了 7 位。

另一种方法是每个数字准确存储 57 位并将这些数字紧密地打包在一起。每个存储的 8 个数字可以节省 7 个字节（因此 8 个数字将占用 57 个字节而不是 64 个字节）。但是，恢复原始数字会稍微复杂一些。

我缺乏知识不允许我谈论任何可以做得更好的方法。

Answer 2

粗略估计：3 位足以编码 0..7，因此 3 ⋅ 20 = 60 位足以编码 0..7 ²⁰。更准确：⌈log ₂ 7 ²⁰ ⌉ = 57 位就足够了。

如果要编码的数字均匀分布在此范围内，您将无法做得更好。否则，您可以通过为更常见的数字提供更短的代码来平均做得更好。