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;
}
我改寫的內容不能按預期工作。爲了測試實現，在main（）中，我嘗試了一個bitset_lookup，期望返回值爲0或1，但是我得到的值爲32.我相信這肯定與我使用指針有關，儘管我看不到我我做錯了。
任何幫助表示讚賞！
這是調試器可以提供幫助的地方。 –
1）不要使用有符號整數爲bitshifts /屏蔽，如果你不知道的負面影響的。 2）如果你使用固定寬度類型，則使用固定寬度類型。 3）'WORDSIZE'和'sizeof（int）'之間沒有關係。 4）如果是那樣的話，忘了它並得到一個更好的... – Olaf