通过“tribool”我了解一个可以包含以下值之一的变量：true,false或null.
在问题Copying array of ints vs pointers to bools中,OP希望有一个数组的摩擦(或多或少),尽可能的小.
使用“一点点”最基本的bit-fu,我提出了一个解决方案,每个tribool使用2位,允许在16个字节中存储OP的64个tribools数组,这是可以的.
我使用的摩托车力学很简单,就像：
> boolean A表示“null或not null”,
> boolean B表示“true或false if not null”.
但是后来我以为…一个“位”的算法定义是：
A bit is the amount of information which specifies which of two equally probable events shall occur.
显然,真/假值是1位大.两个真假值作为一个整体是2位大.
而我们的概念性的tribool呢？
我的观点是：在包含的信息的大小方面,一个tribool大于1位,但小于2位.
>理由1：假设我们实现了如上所述的布尔值.如果布尔值A为“null”,则布尔值B的值是多余的,并且不携带任何相关信息.
理由2：将信息从两个独立的布尔值存储在一个tribool是不可能的,所以它有
(以上都没有一个正式的证明,但是我相信我们可以同意,三菱的“大小”严格大于1比特,严格小于2.)
我的问题是：
如何编程地利用一个事实,即一个tribool的信息少于2位,并且在软件(c,c？)中实现一个N个三轴组件,这些数组的内存占用小于N / 4个字节.
是的,我明白这样的一个实现并不是真正的硬件友好的,而且比任何常见的冗余解决方案(如OP的问题中提出的)都要慢.我们只是优化空间,而不是为了效率.
显然,这种实现需要一个不同于一对布尔的tribool表示(如前所述,它们本身是冗余的).该理论说可以实现这一目标,我喜欢看到一个实际的实现.有任何想法吗？
解决方法
想到这一点的最简单的方法是将您的“tribools”数组编码为基数3中的数字. 0 = FALSE,1 = TRUE,2 = NULL.那么以下数组：
{TRUE,FALSE,NULL,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个tribools,所以你可以以4个字节存储N = 20个数组(其中N / 4是5).
