C语言实现位集合存储[0,127]无重复数遇符号位问题及解决

初始实现代码 #

结构体定义 #

typedef struct set
{
    char *blocks;
    char *numbers;
    char blockNum;
};

集合创建函数 #

void createSet(set *newSet)
{
    newSet->blockNum = 1;
    newSet->blocks = calloc(newSet->blockNum, BYTE_SIZE);
}

需求说明：存储[0,127]范围内的无重复数字，通过将对应位置的bit设为1实现，读取时检查bit是否为1判断数字是否在集合中。

元素添加函数 #

void addItem(set *set, unsigned int item)
{
    int blocksToAdd = 0;
    int i = 0;
    int r = (item / BYTE_SIZE);
    int rem=item % BYTE_SIZE;
    if (r > set->blockNum)
    {
        if(r!=0) {
            blocksToAdd = r - (set->blockNum);
        }
        set->blocks = realloc(set->blocks, (set->blockNum + blocksToAdd)*BYTE_SIZE);
    }
    *(set->blocks+r)  = (1 << rem);
}

遇到的问题 #

添加数字7时，*blocks的值为-128而非预期的128。原因是此时*blocks的二进制为1000 0000，而char是有符号类型，最高位为符号位，导致数值被解析为负数。

尝试过以下修复代码，但未解决问题：

int num =*(set->blocks+r);
if(num<0) {
    set->blocks = (char *)realloc(set->blocks, (set->blockNum + 1)*BYTE_SIZE);
    num*=-1;
    *(set->blocks+r)  = num;
}

最终解决方案 #

将blocks的类型从char*改为unsigned char*，避免符号位干扰；同时初始分配16字节内存，减少后续realloc的调用次数优化效率，后续可再考虑内存缩减。

内容的提问来源于stack exchange，提问作者Oriel sher