清除位时唯一的最大不同字节值集

否。对于8位值,使用四位是最佳选择。

如果您有70个4位值,并决定添加一个5位值作为有效值,那么您必须放弃通过清除一位可以创建的五个4位值。类似地,如果想要一个有效的3位值,还必须放弃五个4位值。

如果可以增加位数,则可以增加可能值与所用位数的比率。

由于只有256个可能的值和8个可能的总体,因此测试所有可能的总体计数是一项微不足道的任务:

#include <stdio.h>
#include <stdint.h>

int popcount( uint8_t byte )
{
    int count = 0 ;
    for( uint8_t b = 0x01; b != 0; b <<= 1 )
    {
        count = count + (((byte & b) != 0) ? 1 : 0) ;
    }

    return count ;
}

int main()
{
    int valuecount[8] = {0} ;
    for( int i = 0; i < 256; i++ )
    {
        valuecount[popcount(i)]++ ;    
    }

    printf( "popcount\tvalues\n") ;
    for( int p = 0; p < 9; p++ )
    {
        printf( "   %d\t\t  %d\n", p, valuecount[p] ) ;
    }

    return 0;
}

结果:

popcount        values 
   0              1
   1              8
   2              28
   3              56
   4              70
   5              56
   6              28
   7              8
   8              1

任意字长的最佳总体计数 n 始终是 n / 2 . 对于16位,具有8个1位的值的数目为12870。