如何在最大化有效性的同时,将3态位运算符按位实现到任意大小的内存？

Question

我可以使用2位到每个3状态位来实现它,[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%)

我如何能够对任意大小的数据实现类似的3态按位方法,并最大限度地提高大小的有效性？如果我将数据用作uints的数组并对它们使用这种方法,我只会获得20%的有效性.(如果数据的大小不乘以4,则降低)

注意:我唯一需要的是尺寸有效性,我不关心速度性能.(好吧,除非你选择使用BigInteger而不是uint)

Answer 1

log32 是无关紧要的.

表示3值单位的最大可能效率是每单位的比特,并且每单位2比特的压缩是大约20.75%.所以20%是相当不错的.log23(2-log23))/2

你不应该pow用于整数求幂; 除了缓慢之外,它有时会被1ULP关闭,一旦你将它强制转换为整数,它就足以让它关闭1.但是也没有必要做所有这些工作; 您可以将五个3状态值压缩为一个byte(),并且可以直接构建一个包含256个条目的查找表,每个可能的字节值一个.35 = 243 < 256

使用LUT,您可以从大型向量中提取3态值:

/* 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的数据向量),那么将其压缩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;
}