为空间优化一系列tribools

Question

让我先从一些背景知识开始:

通过"tribool"我理解一个可以包含以下值之一的变量:true,false或null.

问题是复制int的数组与指向 bool的指针,OP希望有一个尽可能小的tribools数组(或多或少).

使用"一点点"最基本的bit-fu,我提出了一个解决方案,每个tribool使用2位,并允许以16个字节存储OP的64个tribool数组,这是可以的.

我使用的tribool机制非常简单,如:

但后来我想......"比特"的算法定义是:

阿位是指定其中两个同样可能的事件应发生的信息量.

显然,真/假值是1位大.两个真假值整体上是2位大.

那么我们的概念摩擦呢呢？

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

(以上都不是正式的证据,但我相信我们可以同意关于tribool的"大小"严格大于1位且严格小于2.)

我的问题是:

如何以编程方式利用tribool信息少于2位的事实,并在软件(c,c ++？)中实现一个N tribool数组,其内存占用量小于N/4某些N的字节数？

是的,我确实理解这样的实现并不是真正的硬件友好,并且执行速度比任何具有冗余的常见解决方案都要慢(如OP的问题所示).让我们优化空间,而不是效率.

显然,这种实现需要一种摩博尔的不同表示而不是一对bool(这本身就是多余的,如前所述).该理论认为可以实现这一目标,我希望看到实际的实施.有任何想法吗？

Answer 1

你的直觉是正确的,这当然是可能的.这基本上是算术编码的一种形式,或者至少是它的简单实例.

想到它的最简单方法是想象将"tribools"数组编码为基数3中的数字 - 例如0 = FALSE,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),因此使用此方法可以存储20位32位的tribools - 因此您可以存储N=204个字节的数组(其中N/45位).

我能看到的唯一缺点是检索一个tribool值的复杂性(比如说例如索引3处的tribool).这可以单独完成,还是最好解码整个数据包(假设每包32位)并以某种方式缓冲它？ (2认同)