c++ - 为空间优化 tribools 数组

Question

让我从一些背景开始:

对于“tribool”，我理解的变量可以包含以下值之一:true、false 或 null。

有问题Copying array of ints vs pointers to bools , OP 希望拥有尽可能小的 tribools 数组(或多或少)。

有了“一点点”最基本的 bit-fu，我想出了一个解决方案，每个 tribool 使用 2 位，并允许以 16 字节存储 OP 的 64 tribool 数组，这没问题。

我使用的 tribool 机制很简单，例如:

• boolean A 表示“null or not null”，
• boolean B 表示“如果不为空则为真或假”。

---

但后来我想...“位”的算法定义是:

A bit is the amount of information which specifies which of two equally probable events shall occur.

很明显，true/false 值大 1 位。两个 true-false 值作为一个整体是 2 bit big。

那我们的概念三元组呢？

我的观点是:就包含信息的大小而言，tribool 大于 1 位但小于 2 位。

• 理由 1:假设我们按上述方式实现了 if bool 值。如果 bool 值A为“null”，则 bool 值B的值是多余的，不携带任何相关信息。
• 理由 2:不可能将 2 个独立的 bool 值的信息存储在一个 tribool 中，所以它有

(以上都不是正式证明，但我相信我们可以同意关于tribool的“大小”严格大于1位且严格小于2位。)

---

我的问题是:

如何以编程方式利用 tribool 的信息少于 2 位这一事实，并在软件中实现(c、c++？)一个包含 N 个 tribool 的数组，它具有对于某些 N，内存占用小于 N/4 字节？

是的，我知道这样的实现并不是真正的硬件友好型，并且比任何具有冗余的常见解决方案(如 OP 的问题中所提出的)执行得都慢。让我们只针对空间进行优化，而不是针对效率进行优化。

很明显，这个实现需要一个与一对 bool 值不同的 tribool 表示(如前所述，它本身是多余的)。该理论表明实现该目标是可能的，我希望看到实际的实现。有什么想法吗？

Answer 1

你的直觉是正确的，这当然是可能的。这基本上是 arithmetic coding 的一种形式，或者至少是它的一个简单实例。

想到它的最简单方法是想象将“tribools”数组编码为基数为 3 的数字 - 例如0=假，1=真，2=空。然后是以下数组:

{TRUE, FALSE, NULL, NULL, FALSE, FALSE, TRUE}

编码为数字

1022001

然后您可以以正常方式将其转换为十进制:

(1*3^0)+(0*3^1)+(0*3^2)+(2*3^3)+(2*3^4)+(0*3^5)+(1*3^6) = 946

每个 tribool 占用 ln(3)/ln(2) 位(大约 1.58)，因此使用此方法您可以在 32 位中存储 20 个 tribool - 因此您可以存储 N=20 4 个字节的数组(其中 N/4 为 5)。