Closed. This question does not meet
Stack Overflow guidelines 。它目前不接受答案。
想改善这个问题吗？更新问题，使其成为 Stack Overflow 的
on-topic。
4年前关闭。
Improve this question
以下创建和使用位集的代码来自以下教程
"Intro to Bit Vectors" 。我正在重写此代码以尝试学习和了解有关 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。我相信这一定与我使用指针有关，尽管我看不到我的我做错了。
任何帮助表示赞赏!
那不是教程，充其量只是误导性示例。
首先，使用无符号类型。我推荐 unsigned long (出于各种原因，它们都不重要)。 <limits.h> 头文件定义了常量 CHAR_BIT ，您可以在任何无符号整数类型中使用的位数始终是 CHAR_BIT * sizeof (unsigned_type) 。
其次，您可以通过将大小信息添加到结构中来使位图(或有序位集)动态调整大小。
以上归结为
#include <stdlib.h>
#include <limits.h>
#define ULONG_BITS (CHAR_BIT * sizeof (unsigned long))
typedef struct {
size_t ulongs;
unsigned long *ulong;
} bitset;
#define BITSET_INIT { 0, NULL }
void bitset_init(bitset *bset)
{
if (bset) {
bset->ulongs = 0;
bset->ulong = NULL;
}
}
void bitset_free(bitset *bset)
{
if (bset) {
free(bset->ulong);
bset->ulongs = 0;
bset->ulong = NULL;
}
}
/* Returns: 0 if successfully set
-1 if bs is NULL
-2 if out of memory. */
int bitset_set(bitset *bset, const size_t bit)
{
if (bset) {
const size_t i = bit / ULONG_BITS;
/* Need to grow the bitset? */
if (i >= bset->ulongs) {
const size_t ulongs = i + 1; /* Use better strategy! */
unsigned long *ulong;
size_t n = bset->ulongs;
ulong = realloc(bset->ulong, ulongs * sizeof bset->ulong[0]);
if (!ulong)
return -2;
/* Update the structure to reflect the changes */
bset->ulongs = ulongs;
bset->ulong = ulong;
/* Clear the newly acquired part of the ulong array */
while (n < ulongs)
ulong[n++] = 0UL;
}
bset->ulong[i] |= 1UL << (bit % ULONG_BITS);
return 0;
} else
return -1;
}
/* Returns: 0 if SET
1 if UNSET
-1 if outside the bitset */
int bitset_get(bitset *bset, const size_t bit)
{
if (bset) {
const size_t i = bit / ULONG_BITS;
if (i >= bset->ulongs)
return -1;
return !(bset->ulong[i] & (1UL << (bit % ULONG_BITS)));
} else
return -1;
}
在
bitset 结构中，
ulong 是动态分配的
ulongs
unsigned long 数组。因此，它存储
ulongs * ULONG_BITS 位。
BITSET_INIT 是一个预处理器宏，可用于初始化空位集。如果你不能或不想使用它，你可以使用
bitset_init() 来初始化一个 bitset。两者是等价的。
bitset_free() 释放为 bitset 分配的动态内存。调用后，位集消失了，使用的变量重新初始化。 (请注意，在未使用但已初始化的位集上调用
bitset_free() 是完全可以的，因为调用
free(NULL) 是完全安全的并且什么都不做。)
由于操作系统/内核会自动释放程序使用的所有内存(某些类型的共享内存段除外)，因此不必在程序退出前立即调用
bitset_free()。但是，如果您将位集用作某些算法的一部分，那么释放不再需要的内存显然是一个好习惯，这样应用程序就可以无限期地运行而不会“泄漏”(浪费)内存。
bitset_set() 会在必要时自动增加位集，但只会增加到需要的大小。这不一定是一个好的重新分配策略:
malloc()/
realloc() 等调用相对较慢，如果您碰巧按递增顺序(通过增加位数)调用
bitset_set() ，您最终会为每个
realloc() 调用
ULONG_BITS 。相反，向上调整新大小 (
ulongs ) 通常是一个好主意——您为此使用的确切公式是您的重新分配策略——但建议一个好的策略需要使用实际程序进行实际测试。显示的一个有效，并且非常健壮，但在某些情况下可能会有点慢。 (不过，您至少需要使用数万位。)
bitset_get() 函数的返回值很时髦，因为我希望该函数为“未设置”和“在位设置之外”返回相似的值，因为两者在逻辑上是相似的。 (也就是说，我认为位集是一组设置位；在这种情况下，将集合之外的所有位视为未设置是合乎逻辑的。)
一个更传统的定义是
int bitset_get(bitset *bset, const size_t bit)
{
if (bset) {
const size_t i = bit / ULONG_BITS;
if (i >= bset->ulongs)
return 0;
return !!(bset->ulong[i] & (1UL << (bit % ULONG_BITS)));
} else
return 0;
}
仅对设置的位返回 1，对设置外的位返回 0。
注意
!! 。它只是两个非运算符，没什么奇怪的；使其成为非非运算符。如果
!!x 为零，则
x 为 0，如果
x 非零，则为 1。
(如果
!x 为零，则单个非运算符
x 产生 1，如果
x 非零则产生 0。不应用两次会产生我上面解释的非非。)
要使用上述内容，请尝试例如
int main(void)
{
bitset train = BITSET_INIT;
printf("bitset_get(&train, 5) = %d\n", bitset_get(&train, 5));
if (bitset_set(&train, 5)) {
printf("Oops; we ran out of memory.\n");
return EXIT_FAILURE;
} else
printf("Called bitset_set(&train, 5) successfully\n");
printf("bitset_get(&train, 5) = %d\n");
bitset_free(&train);
return EXIT_SUCCESS;
}
因为我们不对我们正在运行的硬件或系统做任何假设(除非我在某个地方搞砸了；如果你注意到我做了，请在评论中告诉我，这样我就可以解决我的问题!)，并且只有 C 标准所说的内容我们可以依靠，这应该适用于您可以使用符合标准的编译器编译代码的任何内容。 Windows、Linux、BSD、旧的 Unix、macOS 等。
通过一些更改，它甚至可以用于微 Controller 。我不确定是否所有的开发库都有
realloc() ；甚至
malloc() 也可能不可用。除此之外，在 32 位 ARM 之类的东西上，这应该可以正常工作；在 8 位 AVR 上，最好使用
unsigned char 和
CHAR_BIT ，因为它们倾向于模拟更大的类型，而不是在硬件中支持它们。 (上面的代码可以工作，但比必要的要慢。)
个人中心
文章发布
退出
27
4
0
我是一名优秀的程序员,十分优秀！