реализовать бит-карту в следующей ситуации

Question

Мой вопрос заключается в том, как реализовать бит-карту в следующей ситуации?
Если вершина графа находится в минимальном остовном дереве (MST), отметьте соответствующий бит; позже проверьте, находится ли он в MST, проверив бит.

В начале я думал об использовании

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

bit bitmap[num_of_vertex];  

и использовать массив растровых изображений для записи бита;

Но тогда я обнаружил, что sizeof (bitmap [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

о битовой карте, вот пример по программированию Pearls, и я добавил некоторые примечания:

#define BITPERWORD 32 //bits of int，which depends on your computer 
#define N   10000000 // number of your elements 
#define SHIFT  5 // 32 = 2^5 
#define MASK  0x1F // 11111 in binary 
int a[N/BITPERWORD + 1]; //space for your bitmap 

// i is the the bit you want to use 
void set(int i)  {  a[i>>SHIFT] |= (1<<(i&MASK));} 
void clr(int i)  {  a[i>>SHIFT] &= ~(1<<(i&MASK));} 
int test(int i) { return a[i>>SHIFT] & (1<<(i&MASK));} 

и не забывает инициализацию в начале:

for(i=0;i<N;i++) 
    clr(i); 

Answer 2

Ситуация в том, что вы просто не можете иметь 1-битные типы в C. Наименьший адресуемый блок является байтом в C, поэтому, даже если вы объявите структуру с однобитовым битовым полем, это будет заполненный байтом (по крайней мере). Что вы можете сделать, так это создать массив байтов, а затем получить доступ к битам в массиве с использованием деления и модуля.

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; 
}