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

Question

我正在创建一种数据格式，它将存储在 DS2431 单线 EEPROM 中。一页将使用 EPROM 仿真模式（其中一旦写入的数据只能通过清除位进行修改）。在此页面中，我想存储一个带有 ID 的字节，该 ID 不能更改为另一个有效值（因为只允许清除位）。

我正在考虑使用 popcount 为 4 的一组值（有 70 个不同的值）。清除任何位意味着 popcount 不再是 4，因此这满足所需的属性.

但是能否找到一组具有 70 多个不同值且满足属性的字节值？

Answer 1

没有。对于 8 位值，使用四位是最佳选择。

如果您有 70 个 4 位值并决定添加一个 5 位值作为有效值，则您必须放弃可以通过清除位创建的五个 4 位值。同样，如果你想要一个有效的 3 位值，你也必须放弃五个 4 位值。

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

Answer 2

由于只有 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。

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

Largest set of different byte values unique when clearing bits

embedded

bits

data-representation