c++ - 使用较少位的无符号 qword(64 位)的值范围？

Question

我正在寻找一种表示以下值范围的方法:0 - 18446744073709551615使用少于 8 个字节。

我试过想一些方法可以做到，但没有任何效果。理论上，例如:用一个字节来表示至少2个字节的位序列。然而，2 个字节有 65536 个不同的位组合，而一个字节只给我们一个值范围 0-255(256 种组合)。

最好的方法可能是更改位的含义。那会很好，但不能有任何精度损失。

我开始认为这根本不可能，尽管我想听听其他人对这个问题的看法和理论。

有两条规则:#1 不能有任何精度损失(即所有数字 0 - 18446744073709551615 必须是可表示的)。#2 从标准 64 位格式进行的转换永远不会导致需要超过 7 个字节(56 位)。

这些规则使这变得特别困难。

Answer 1

these rules make this particularly hard.

是的，很难证明是不可能的。

如果对于每个 可能的 64b 值，您可以无损地将 8 个字节压缩到少于 8 个字节，您可以继续重复该过程，直到您的 1TB 文件压缩到大约 7 个字节。

还有很多其他信息论论证为什么这是不可能的。例如鸽巢原则:n 位只有 2^n 个独特的位模式，因此任何小于 64 位的东西都不能对每个可能的 64 位值都有唯一的表示。

---

您可以使用的是 Huffman coding或类似:如果某些 64b 值比其他值更常见，则不太复杂的可变长度编码方案可以节省总字节数。 但要使用可变长度编码方案表示所有 64b 值，某些值的编码将占用超过 8 个字节。

存在更高级的熵编码方法，并用于现代视频编解码器。 (例如 x264 的 CABAC)。

---

有关更多理论，维基百科的无损压缩文章有一个 Limitations section .

另见:

• cstheory.SE: Which is the limit of lossless compression data? (if there exists such a limit)

• Kolmogorov complexity