1

Linux C でビットマップ API が必要です。

2^18 ビットが必要なので、32KB のメモリが必要です。また、ビットマップ内のビットを頻繁に設定および設定解除します。

したがって、基本的に次のような API が必要です。

set_bitmap(int i)  // it sets the i-th bit to 1 in the bitmap
unset_bitmap(int i) // it sets the i-th bit to 0 in the bitmap
bitmap_t create_bitmap(int n) // it creates a bitmap of size n, like n=2^18

ソースコードまたは類似のソースコードはありますか?

ありがとう!

4

3 に答える 3

11

これは難しくありません。

typedef unsigned char* bitmap_t;

void set_bitmap(bitmap_t b, int i) {
    b[i / 8] |= 1 << (i & 7);
}

void unset_bitmap(bitmap_t b, int i) {
    b[i / 8] &= ~(1 << (i & 7));
}

void get_bitmap(bitmap_t b, int i) {
    return b[i / 8] & (1 << (i & 7)) ? 1 : 0;
}

bitmap_t create_bitmap(int n) {
    return malloc((n + 7) / 8);
}
于 2013-06-05T18:52:28.000 に答える
1

function の他の回答に間違いがあるようget_bitmapです。ビット検出は次のように行う必要があります。

b[i / 8] & (1 << (i & 7))

修正されたコード全体は次のようになります。

typedef unsigned char* bitmap_t;

void set_bitmap(bitmap_t b, int i) {
    b[i / 8] |= 1 << (i & 7);
}

void unset_bitmap(bitmap_t b, int i) {
    b[i / 8] &= ~(1 << (i & 7));
}

int get_bitmap(bitmap_t b, int i) {
    return b[i / 8] & (1 << (i & 7)) ? 1 : 0;
}

bitmap_t create_bitmap(int n) {
    return malloc((n + 7) / 8);
}
于 2014-10-14T12:33:58.060 に答える