Quick example of using a bitset to determine free indices in something (e.g., a cache of reusable objects, maybe a memory pool, etc.)

bitalloc.c

#include <stdint.h>
#include <stdio.h>

#define OBJ_UNUSED_BITS_MAX 8

static uint32_t obj_unused_bits[OBJ_UNUSED_BITS_MAX] = { 0 };

int obj_first_unused()
{
  // Based off the code at Sean Eron Anderson's bit twiddling hacks page, in
  // particular:
  // http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
  static const int de_bruijn_bits[32] = {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27,
    13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };

  int index = 0;

  for (; index < OBJ_UNUSED_BITS_MAX; ++index) {
    const uint32_t bits = ~obj_unused_bits[index];
    if (bits) {
      return index * 32 + de_bruijn_bits[((bits & -bits) * 0x077CB531U) >> 27];
    }
  }

  return -1;
}

int obj_alloc_bit(int index)
{
  const int bit_index = index / 32;
  if (index < 0 || index / 32 >= OBJ_UNUSED_BITS_MAX) {
    return -1;
  } else {
    const int shift = index % 32;
    const int previous = (obj_unused_bits[bit_index] >> shift) & 0x1U;
    obj_unused_bits[bit_index] |= 0x1U << shift;
    return previous;
  }
}

int obj_dealloc_bit(int index)
{
  const int bit_index = index / 32;
  if (index < 0 || index / 32 >= OBJ_UNUSED_BITS_MAX) {
    return -1;
  } else {
    const int shift = index % 32;
    const int previous = (obj_unused_bits[bit_index] >> shift) & 0x1U;
    obj_unused_bits[bit_index] &= ~(0x1U << shift);
    return previous;
  }
}


int main(int argc, char const *argv[])
{
  int index;

  printf("Next available index: %d\n", obj_first_unused()); // 0

  printf("Alloc %d: %d\n", 0, obj_alloc_bit(0));
  printf("Next available index: %d\n", obj_first_unused()); // 1

  printf("Alloc %d: %d\n", 1, obj_alloc_bit(1));
  printf("Next available index: %d\n", obj_first_unused()); // 2

  printf("Alloc %d: %d\n", 3, obj_alloc_bit(3));
  printf("Next available index: %d\n", obj_first_unused()); // 2

  printf("Alloc %d: %d\n", 4, obj_alloc_bit(4));
  printf("Next available index: %d\n", obj_first_unused()); // 2

  printf("Alloc %d: %d\n", 2, obj_alloc_bit(2));
  printf("Next available index: %d\n", obj_first_unused()); // 5

  for (index = 5; index < 256; ++index) {
    obj_alloc_bit(index);
  }
  printf("Next available index: %d\n", obj_first_unused()); // -1 (all consumed)

  printf("Dealloc %d: %d\n", 123, obj_dealloc_bit(123));
  printf("Next available index: %d\n", obj_first_unused()); // 123

  printf("Dealloc %d: %d\n", 256, obj_dealloc_bit(256));

  return 0;
}