1
ビットセットを作成して使用する以下のコードは、次のチュートリアル"Intro to Bit Vectors"からのコードです。私はこのコードを書き直して、Cの構造体とポインタについてもっと学び、理解しようとしています。Cでビットセットを実装する方法
#include <stdio.h>
#include <stdlib.h>
#define WORDSIZE 32
#define BITS_WORDSIZE 5
#define MASK 0x1f
// Create a bitset
int initbv(int **bv, int val) {
*bv = calloc(val/WORDSIZE + 1, sizeof(int));
return *bv != NULL;
}
// Place int 'i' in the biset
void set(int bv[], int i) {
bv[i>>BITS_WORDSIZE] |= (1 << (i & MASK));
}
// Return true if integer 'i' is a member of the bitset
int member(int bv[], int i) {
int boolean = bv[i>>BITS_WORDSIZE] & (1 << (i & MASK));
return boolean;
}
int main() {
int *bv, i;
int s1[] = {32, 5, 0};
int s2[] = {32, 4, 5, 0};
initbv(&bv, 32);
// Fill bitset with s1
for(i = 0; s1[i]; i++) {
set(bv, s1[i]);
}
// Print intersection of bitset (s1) and s2
for(i = 0; s2[i]; i++) {
if(member(bv, s2[i])) {
printf("%d\n", s2[i]);
}
}
free(bv);
return 0;
}
以下は、構造体を使用するために書き直したものです。
#include <stdio.h>
#include <stdlib.h>
#define WORDSIZE 32
#define BITS_WS 5
#define MASK 0x1f
struct bitset {
int *bv;
};
/* Create bitset that can hold 'size' items */
struct bitset * bitset_new(int size) {
struct bitset * set = malloc(sizeof(struct bitset));
set->bv = calloc(size/WORDSIZE + 1, sizeof(int));
return set;
}
/* Add an item to a bitset */
int bitset_add(struct bitset * this, int item) {
return this->bv[item>>BITS_WS] |= (1 << (item & MASK));
}
/* Check if an item is in the bitset */
int bitset_lookup(struct bitset * this, int item) {
int boolean = this->bv[item>>BITS_WS] & (1 << (item & MASK));
printf("%d\n", boolean);
return boolean;
}
int main() {
struct bitset * test = bitset_new(32);
int num = 5;
bitset_add(test, num);
printf("%d\n", bitset_lookup(test, num));
return 0;
}
私が書き直したものは期待通りに動作していません。インプリメンテーションをテストするために、私はbitset_lookupを試して、0または1の戻り値を期待しますが、32の値を得ます。ポインタの使用とは何か関係があります。間違っている。
これは、デバッガが役立つところです。 –
1）否定的なことに気付かない場合は、ビットシフト/マスキングに符号付き整数を使用しないでください。 2）あなたが固定したい場合は、固定幅タイプを使用します。 3） 'WORDSIZE'と' sizeof（int） 'には関係がありません。 4）それがトゥルーリアのものであれば、それを忘れて、より良いものを手に入れよう。 – Olaf