Bitmaps are incredibly handy data structures, and everyone should have one in their back pocket. If you don’t have one, feel free to use mine. Feel free to offer improvements to mine.

https://github.com/ryanlayer/cs/tree/master/bitmap

Many others have developed methods that probably perform better and have more features. My intent is mostly educational. I will try to keep a running list here:

https://github.com/attractivechaos/klib/pull/59 h/t @jomarnz
https://github.com/lemire/cbitset h/t @brent_p

The most straight-forward way to implement a bitmap is with an array of unsigned ints. Here I use 32-bits. Once you have your bag of bits, you need to pick the ‘endianness’ of your map, which defines the order bits are stored in. You can put the first bit, b[0], on the LITTLE end (little-endian) like so:

0 0 0 0 0 0 0 1

or on the BIG end (big-endian) like so:

1 0 0 0 0 0 0 0

I use big-endian because, well I don’t know why. Maybe when I was debugging this it made more sense when I printed out the bits in big-endian. It doesn’t really matter, as long as your bit shifts for getting and setting agree.

To set a bit i, you divided by 32 to get to the element of the array containing that bit then OR that element with a 1 that has has been shifted. The MOD gives the local position of that bit in the element and I subtract that from 31 to put it on the big end.

b[i/32] |= 1 << (31 - (i%32));

You might think that the 31 above should be a 32 because, you know, 32-bits. Consider when i = 0, which would be 1 << (32 - 0 ) = 4294967296. 4294967295 is the max value for an unsigned 32-bit int, so 4294967296 would require 33 bits. Overflow.

To get the bit you jump to the element in the same way, then shift that value over until i is at the least significant bit, then AND that value with 1 to mask out any trailing bits.

b[i/32]) >> (31 - (i%32)) & 1)

To make things easier, my bitmap tracks the number of bits in the map and the number of ints needed to represent those bits. This allows me to grow the map dynamically. If you want to set a bit that is outside the current range, I grow the array exponentially until the bit fits. If you want to get a bit that is outside the current range I just return zero instead of growing the map. There are also functions to save and load maps from disk.

Start by initializing the bitmap with some starting size, this can be just a guess on how big it will bet but don’t worry if it is too small, the map will grow as needed. Then set and get to your heart’s content. When you are done you can save it for later or just destroy it. If you do have a saved map, then load it and you are good to go.

Obvious additions to the library are bitwise operations (AND, OR, etc.), compressed storage, and on-demand loading from disk.

TL;DR

Function singnatures:

struct bit_map *bit_map_init(uint64_t bits);
struct bit_map *bit_map_load(char *file_name);
void bit_map_store(struct bit_map *b, char *file_name);
void bit_map_destroy(struct bit_map **b);
void bit_map_set(struct bit_map *b, uint64_t i);
uint32_t bit_map_get(struct bit_map *b, uint64_t q);

A sample program:

#include "bitmap.h"

int main(int argc, char **argv)
{
    uint64_t starting_size = 8;

    struct bit_map *b = bit_map_init(starting_size);

    printf("b[0]: %d\n", bit_map_get(b, 0));

    printf("b[0] = 1\n");
    bit_map_set(b, 0);

    printf("b[0]: %d\n", bit_map_get(b, 0));

    printf("b[1000] = 1\n");
    bit_map_set(b, 1000);

    printf("b[999]: %d\n", bit_map_get(b, 999));
    printf("b[1000]: %d\n", bit_map_get(b, 1000));
    printf("b[9000]: %d\n", bit_map_get(b, 9000));

    bit_map_store(b, "bitmap.data");

    bit_map_destroy(&b);

    struct bit_map *d = bit_map_load("bitmap.data");

    printf("d[0]: %d\n", bit_map_get(d, 0));
    printf("d[999]: %d\n", bit_map_get(d, 999));
    printf("d[1000]: %d\n", bit_map_get(d, 1000));
    printf("d[9000]: %d\n", bit_map_get(d, 9000));

    bit_map_destroy(&d);
}

Program output:

b[0]: 0
b[0] = 1
b[0]: 1
b[1000] = 1
b[999]: 0
b[1000]: 1
b[9000]: 0
d[0]: 1
d[999]: 0
d[1000]: 1
d[9000]: 0