c++ - 优化空间的Tribool数组

让我从一些背景开始:

通过“tribool”，我理解了一个变量，该变量可以包含以下值之一:true，false或null。

问题Copying array of ints vs pointers to bools，OP希望有一个Tribools数组(或多或少)，该数组应尽可能小。

通过“最基本的位”，我提出了一个解决方案，该方案每个tribool使用2位，并允许以16个字节存储OP的64个tribools数组。

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

boolean A表示“null or not null”，

bool 型B的意思是“如果不为null，则为true或false”。

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

显然，true/false值是1位大。总体上，两个真假值均为2位大。

那我们的概念书呢？

我的观点是:就所包含信息的大小而言，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个Tribool的内存占用小于N/4字节吗？

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

显然，这种实现方式需要一对三元组而不是一对 bool 元组(如前所述，它本身是多余的)。理论上说有可能实现这个目标，我希望看到一个实际的实现。有任何想法吗？

最佳答案

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

最简单的方法是想象将“tribools”数组编码为以3为底的数字-例如0 =否，1 = TRUE，2 = NULL。然后是以下数组:

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

编码为数字

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

(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-这样就可以在4个字节中存储N=20数组(其中N/4为5)。