下面的代码创建并使用了一个位集,它来自以下教程"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