c++ - 如何在最大化大小效率的同时将三态位运算符按位实现到任意大小的内存？

Question

我可以对每个 3 态位使用 2 位来实现它，[00 - 第一，10 - 第二，11\01 - 第三]，但是当启用第二位时，第一位就没用了。理论上，有一种实现在大小上比这种方法(我提到的 2 位)好 37%。 (即 1-log3(2))

我已经尝试过的代码:

#define uint unsigned int

uint set( uint x, uint place, uint value ) {
    double result = ( double )x;
    result /= pow( 3, place );
    result += value - ( ( uint )result ) % 3;
    return result * pow( 3, place );
}
uint get( uint x, uint place ) {
    return ( ( uint )( ( ( double )x ) / pow( 3, place ) ) ) % 3;
}

int main( ) {
    uint s = 0;
    for ( int i = 0; i < 20; ++i )
        s = set( s, i, i % 3 );
    for ( int i = 0; i < 20; ++i )
        printf( "get( s, %d ) -> %u\n", i, get( s, i ) );
}

打印:

get( s, 0 ) -> 0
get( s, 1 ) -> 1
get( s, 2 ) -> 2
get( s, 3 ) -> 0
...
get( s, 16 ) -> 1
get( s, 17 ) -> 2
get( s, 18 ) -> 0
get( s, 19 ) -> 1

此方法可节省 20% 的大小。 (1-32/40 - 使用我提到的第一种方法需要 40 位)理论上，当容量增加时，效率也会增加。 (当然是 37%)

如何对任意大小的数据实现类似的三态按位方法并最大化大小有效性？如果我将数据用作 uint 的数组并对它们使用此方法，我将只能获得 20% 的效率。 (如果数据大小未乘以 4，则更低)

注意:我唯一需要的是尺寸效率，我不关心速度性能。 (嗯，除非你选择使用 BigInteger 而不是 uint)

Answer 1

log<sub>3</sub>2是无关紧要的。

表示三值单元的最大可能效率是 log<sub>2</sub>3每单位位数，每单位 2 位的压缩是 (2-log<sub>2</sub>3))/2 ，大约是 20.75%。所以 20% 已经很不错了。

你不应该使用 pow用于整数取幂；除了速度慢之外，它有时会被 1ULP 关闭，一旦您将其强制转换为整数，就足以使其关闭 1。但是也不需要所有这些工作；您可以将五个三态值压缩成一个字节 (3<sup>5</sup> = 243 < 256)，并且可以直接构建一个包含 256 个条目的查找表，每个条目对应一个可能的字节值。

使用 LUT，您可以从大 vector 中提取三态值:

/* All error checking omitted */
uint8_t LUT[243][5] = { {0,0,0,0,0}, {1,0,0,0,0}, ... };
uint8_t extract(const uint8_t* data, int offset) {
  return LUT[data[offset/5]][offset%5];
}

顺便说一下，如果一个 1215 字节的查找表被认为是“大”的(这看起来很奇怪，因为您正在谈论 1GB 的数据 vector )，很容易将它压缩一个因子共 4 个，尽管它使表构造复杂化

/* All error checking omitted */
uint8_t LUT[] = { /* Left as an exercise */ };
uint8_t extract(const uint8_t* data, unsigned offset) {
  unsigned index = data[offset/5] * 5 + offset % 5;
  return (LUT[index / 4] >> (2 * (index % 4))) & 3;
}