1

私の質問は、次の状況でビットマップを実装する方法ですか?
グラフの頂点が最小スパニング ツリー (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 より大きい場合は機能しません。

上記の状況で一般的にビットマップはどのように実装されますか?

4

2 に答える 2

5

状況は、C で 1 ビットの型を持つことができないということです。アドレス指定可能な最小単位は C のバイトであるため、1 ビットのビットフィールドで構造体を宣言しても、バイトにパディングされます (少しでも）。できることは、バイトの配列を作成し、除算とモジュラスを使用して配列内のビットにアクセスすることです。

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;
}
于 2013-06-15T06:39:14.213 に答える
1

ビットマップについては、ここにプログラミングパールの例があり、いくつかのメモを追加しました：

#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);
于 2013-06-15T07:18:33.770 に答える