为空间优化一系列tribools
让我先从一些背景知识开始：
通过“tribool”，我理解一个可以包含以下值之一的变量： true ， false或null 。
有问题的是复制int的数组和指向 bool的指针 ，OP希望有一个尽可能小的tribools数组（或多或少）。
使用“一点点”最基本的bit-fu，我提出了一个解决方案，每个tribool使用2位，并允许以16字节存储OP的64个tribool数组，这是可以的。
我使用的tribool机制非常简单，如：
- boolean A表示“null或not null”，
- boolean B表示“如果不为null则为true或false”。
但后来我想……一个“位”的算法定义是：
一位是指定两个同等可能事件中的哪一个应发生的信息量。
显然，真/假值是1位大。 两个真假值整体上是2位大。
那么我们的概念摩擦呢呢？
我的观点是： 就所包含信息的大小而言，tribool大于1位但小于2位 。
- 理由1：假设我们实现了如上所述的if boolean。 如果布尔A为“null”，则布尔值B的值是多余的，并且不携带任何相关信息。
- 理由2：在一个tribool中存储来自2个独立布尔值的信息是不可能的，所以它有
（以上都不是正式的证据，但我相信我们可以同意关于tribool的“大小”严格大于1位且严格小于2。）
我的问题是：
如何以编程方式利用tribool信息少于2位的事实，并在软件 （c，c ++？）中实现一个N triboolsarrays，对于某些N，其内存占用量小于N/4字节？
是的，我确实理解这样的实现并不是真正的硬件友好，并且执行速度比任何具有冗余的常见解决方案都要慢（如OP的问题所示）。 让我们优化空间，而不是效率。
很明显，这种实现需要一种摩博尔的不同表示而不是一对bool（这本身就是多余的，如前所述）。 该理论认为可以实现这一目标，我希望看到实际的实施。 有任何想法吗？
你的直觉是正确的，这当然是可能的。 这基本上是算术编码的一种forms，或者至少是它的简单实例。
想到它的最简单方法是想象将“tribools”数组编码为基数3中的数字 – 例如0 = FALSE，1 = TRUE，2 = NULL。 然后是以下数组：
{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位32个tribools – 所以你可以存储4个字节的N=20数组（其中N/4是5）。
理论上你可以打包X N状态变量
ln(N^X) / ln M
M状态（或类似LaTeX表示法中的log_M（N ^ X））变量。 为了以二进制数字存储三态变量，上面的公式变为：
ln(3^N) / ln 2
例如，在一个8位字节中，您可以拟合5个三态变量。
当您更加密集地打包变量时，解包/修改这些值会更加困难和缓慢。 在上面的示例中，您必须重新计算整个字节才能更改单个三态变量。
应该注意，5个三态变量的字节非常节省空间。 每个字节的密度保持不变，直到你有一个22字节的包，可以容纳111个三态值，而不是110.但是处理这种包装会很麻烦。
与直接在一个字节中存储4个三态值相比，这是否值得额外工作？
此解决方案要求您预先知道您将拥有多少“非空”值（即在编译期间，或者如果您可以在使空间可用之前开始计算有多少非空值）。
然后您可以通过以下方式对其进行编码：
0表示null 1表示非null，后面跟1或0表示true或false。
这将导致每个tribool最多2位，如果它们全部为空则仅为1位。
@psmears是对的，因为所有3个值都同样可能。 但是，如果它们不是同等可能，或者不是独立的，如果你有足够长的字符串，你可以使用你的2位或任何其他编码并在其上运行gzip 。 这应该将其压缩到大约理论极限。 就像在所有值都为0的限制中一样，它应该不会超过字符串长度的对数。
顺便说一句：我们在这里讨论的是熵 。 在这种情况下的简单定义是-P（0）logP（0）-P（1）logP（1）-P（null）logP（null）。 因此，例如，如果P（0）= P（1）= 1/2，并且P（空）= 0，则熵是1比特。 如果P（0）= 1/2，P（1）= 1/4，P（null）= 1/4，那么熵也是1/2 * 1 + 1/4 * 2 + 1/4 * 2 = 1位。 如果概率为1022 / 1024,1 / 1024,1 / 1024，则熵为（几乎为1）*（几乎为0）+ 10/1024 + 10/1024，约等于20/1024或约为百分之二百有点 ！ 事物越确定，它发生时就会越少，因此所需的存储空间越少。
我喜欢@psmears提出的解决方案，但它的缺点是它比直接方法慢。 你可以使用稍微修改过的版本，它也应该很快：
3 ** 5 == 243，差不多是256.这意味着您可以轻松地在一个字节中压缩5个tribool值。 它具有相同的压缩比，但由于每个字节是独立的，因此可以使用LUT实现：
unsigned char get_packed_tribool(unsigned char pk, int num) { // num = (0..4), pk = (0..242) return LUT[num][pk]; // 5*243 bytes of LUTs }; unsigned char update_packed_tribool(unsigned char old_pk, int num, int new_val) { // new_val = 0..2 return old_pk + (new_val - LUT[num][old_pk])*POW3_LUT[num]; };