使用位图跟踪数组

Question

我有一个大小为 10 的数组

我想跟踪数组中的空闲 space，有人告诉我位图是更好的选择。

例如，索引 2 和 3 为空，我可以在位图中的索引 2 和 3 处记录位 0

如何创建默认为 0 位的大小为 10 的位图？

欢迎提供有关位图的有用链接。

提前致谢

Answer 1

C 没有任何 first-class 对 "bit map" 类型的支持；你将不得不自己实施它。非常简单，只需要使用一个无符号整数数组和一些按位 shifting/logic 运算符即可。

类似于：

typedef struct {
  unsigned int *bits;
  size_t size;
} bitmap;

#define BITS (CHAR_BIT * sizeof (unsigned int))

bitmap * bitmap_new(size_t size)
{
  const size_t length = (size + BITS - 1) / BITS;
  const size_t bytes = length * sizeof (unsigned int);
  bitmap *b = malloc(sizeof *b + bytes);
  if (b != NULL)
  {
    b->bits = (unsigned int *) (b + 1);
    memset(b->bits, 0, length);
    b->size = size;
  }
  return b;
}

bool bitmap_test(const bitmap *b, size_t index)
{
  if (index < b->size)
  {
    const size_t ii = index / BITS;
    const unsigned int ib = index % BITS;
    return (bool) ((b->bits[ii] & (1u << ib)) != 0);
  }
  return false;
}

void bitmap_set(bitmap *b, size_t index)
{
  if (index < b->size)
  {
    const size_t ii = index / BITS;
    const unsigned int ib = index % BITS;
    b->bits[ii] |= (1u << ib);
  }
}

以上内容未经测试，但您应该了解主要思想。

使用位图跟踪数组

Keeping track of array using Bit maps

c

arrays

bitmap

bitmapdata