在以下情况下实现位图

Question

我的问题是如何在以下情况下实现位图？
如果图的顶点在最小生成树(MST)中,则标记相应的位; 稍后通过检查位来检查它是否在MST中.

一开始,我正在考虑使用

typedef struct bit_t{    
   char bit0:1;
} bit;       

bit bitmap[num_of_vertex];     

并使用位图数组来记录该位;

但后来我发现sizeof(位图[num_of_vertex])是num_of_vertex字节,而不是num_of_vertex/8字节.所以它不像我想象的那样节省空间;

到目前为止我用了

long bit_record = 0;   
...
bit_record |= 1<< u;//set vertex as in MST    
...    

然后用以下方法检查顶点是否在MST中:

static bool is_in_MST(int v, int bit_record){   
    int mask = 1 <<  v;   
    if (mask & bit_record)    
        return true;   
    else    
        return false;   
}      

尽管代码有效,但如果num_of_vertex大于32,它将无法工作.

一般情况下如何实现上述情况中的位图？

Answer 1

情况是你不能在C中使用1位类型.最小的可寻址单元是C中的一个字节,所以即使你声明一个带有一位位域的结构,它也会被填充到一个字节(at最小).你可以做的是创建一个字节数组,然后使用除法和模数访问数组中的位.

unsigned char bitmap[0x100] = { 0 };

void set_nth_bit(unsigned char *bitmap, int idx)
{
    bitmap[idx / CHAR_BIT] |= 1 << (idx % CHAR_BIT);
}

void clear_nth_bit(unsigned char *bitmap, int idx)
{
    bitmap[idx / CHAR_BIT] &= ~(1 << (idx % CHAR_BIT));
}

int get_nth_bit(unsigned char *bitmap, int idx)
{
    return (bitmap[idx / CHAR_BIT] >> (idx % CHAR_BIT)) & 1;
}