bitset primer

July 29, 2026

In my previous blog post I wrote about why curl’s bitsets and some people asked to explain a bit more how they work and why I like them so much. So here is a introduction for someone unfamiliar with them.

Revisiting the Problem

Many applications have a few main types of data they need to deal with, but many instances of them. Let’s just call them “Things”. A “thing” has several properties the application needs to manage and often it needs to operate on “all things with prop1 == x”. The question is how you design this for working efficiently on thousands of “Things”.

You could keep all things in a List and traverse the list every time you are looking for “prop1 == x” things. This is very inefficient when only a few things match that check.

You could decide to make two lists: “the things where prop1 == x” and “all the other things”. That works fine until you have to deal with changes to prop1 and need to move things from one list to the other all the time.

And sooner or later there will be need for “things where prop2 == y” to keep track of. Now, you’d need to put things into several lists at the same time.

This becomes messy quite easily, especially when things may also go away again while you are operating on the lists.

Number Them

A Step Back

The one thing that makes all these lists so complicated is that they were managing pointers to things. While every thing has a pointer value, not every pointer value is a thing. And if we use a pointer value that is not a thing, we get intro trouble: segfaults, use-after-free, etc.

(Aside: that is fundamentally what Rust set out to fix. You are free to pass around pointers when no one is allowed to modify the thing. If you want to have a pointer for modification, Rust makes sure that it is this is the only one. Rust does not let you put a thing into two lists unless you break its arms. (Yes, this is simplified.))

Instead, let’s go for the oldest trick in the box: indirection. We assign each thing a number.

For that we keep Things in a Table (e.g. an Array) and use the array index as its number. It will keep this number as long as it exists. The Table is the only place where we keep pointers to Things.

When a Thing is removed, the array entry becomes empty. Someone looking up an old number will see that and can act on it. After a while, we may reuse this array entry again (think of linux file descriptors and process identifiers).

For “all things with prop1 == x”, we then keep a set of numbers. And the cool data structure for a set of numbers is a bitset. They are very efficient and cheap, operate in constant time mostly (e.g. no matter how large) and can be iterated over and updated without any complications.

This elegantly solves our problems of keeping track of things and handle certain subsets efficiently and safely.

Below is an introduction on how they work in case you never used them or want a refresher.

Bitset Primer

Starting Small

Let’s start with a Set that can hold the numbers 0 to 7. As it is a Set, any number can only appear once or not at all. When we realize this data structure as a bitset, we would use a single byte, denoted here by the C type uint8_t.

A very simple bitset

The first set shown is empty, all bits are 0. The second set contains the number 0, 2 and 5 and the bits for those numbers are 1.

Adding, removing and checking numbers would work like this (without boundary checks):

void set_add(struct set *set, uint8_t n) {
 set->data |= (1U << n);
}
void set_remove(struct set *set, uint8_t n) {
 set->data &= ~(1U << n);
}
bool set_contains(struct set *set, uint8_t n) {
 return set->data & (1U << n);
}

If you want to know how many numbers are in a set, e.g. the cardinality, you need to count the number of 1 bits. There are clever algorithms to do that efficiently which I will not cover here[1]. Luckily, many compilers offer support for that already, for example gcc has __builtin_popcount(x). And that may translate into basically a single CPU instruction if the target machine supports it.

int set_count(struct set *set) {
 return __builtin_popcount(set->data);
}

Growing

If you need a larger set, you’d use more data, like in:

A larger, simple bitset

The set now manages 2 bytes, one of the numbers 0..7 and the other for 8..15. The code for adding a number has to change:

void set_add(struct set *set, uint8_t n) {
 uint8_t slot = (n / 8);
 set->data[slot] |= (1U << (n % 8));
}

You divide by 8 (8 because each data holds 8 numbers) to know which array element to use and then shift the bit by modulo 8. The other set methods change accordingly. (Exercise to the reader: you need to check if n is too large for your set.)

We can now make larger sets by having larger data arrays. The code does not really change for this. Until you want to store numbers larger then 255 where you need another argument type to the functions.

If you write code for a modern CPU, you want to change the data type to 64-bit:

64-bit set base type

So, instead of dividing by 8 the set now uses 64 to determine the slot the the bit to manipulate. You’d also switch to __builtin_popcountll(x).

Iterating

You iterate over the members of a bitset by asking it for the smallest number it contains:

bool set_first(struct set *set, uint32_t *pfirst) {
 for(uint32_t i = 0; i < number_of_slots; ++i) {
 if(set->data[i]) {
 *pfirst = (i * 64) + __builtin_ctzll(set->data[i]);
 return TRUE;
 }
 }
 return FALSE;
}

If the set is empty, this returns FALSE. Otherwise pfirst will be assigned the smallest number in the set. How so?

If set->data[i] is not 0, at least one bit in that slot is set. The smallest number in the slot is the lowest 1 bit. Which means all bits lower are 0. We just Count the Trailing Zeros in set->data[i]. This is what __builtin_ctzll(x) does.

Having found the smallest number in the set, we can iterate by asking the set for the next higher number than the last one we got. Like this:

bool set_next(struct set *set, uint32_t last, uint32_t *pnext) {
 uint32_t i;
 uint64_t x;
 ++last; /* the next number must be at least 1 higher */
 i = last / 64;
 x = set->data[i] >> (last % 64);
 if(x) { /* more higher bits are set in this slot */
 *pnext = last + __builtin_ctzll(x);
 return TRUE;
 }
 /* Need to look at the following slots */
 for(i = i + 1; i < number_of_slots; ++i) {
 if(set->data[i]) {
 *pnext = (i * 64) + __builtin_ctzll(set->data[i]);
 return TRUE;
 }
 }
 return FALSE;
}

And we call set_next() until it returns FALSE. End of iteration.

If you study set_next() you’ll see that what it really does is “Give me the smallest number in the set that is higher than ’last’”. It does not matter if last is still in the set or ever has been!

There is no “iteration state” that is somehow connected to the set’s contents. We are free to modify the set at any time. If we add smaller numbers than last they will be ignored for the iteration. If we add larger ones, they will be visited.

If that is fine for you depends on your use case. If you really need a frozen set to iterate over, maybe you could make a copy first. Copies of bitsets are not that expensive.

Other Operations

Set operations like add, subtract or copy of bitsets are cheap as well:

add: iterate set1->data |= set2->data
subtract: iterate set1->data &= ~set2->data
copy: memcpy of the data array.

Summary

We learned how bitsets work. They are efficient data structures, using little memory when dealing with arbitrary sets as long as you know the range of numbers you have to deal with.

We saw that most operations on the set work in constant time, independent of the size of the set. Counting the members in a set might be the most expensive operation. Iterating is most expensive for (nearly) empty sets.

However, the “expensive” operations work on subsequent memory locations, one data slot after the other. Modern CPUs are highly optimized for such access.

Bitsets are a neat, efficient and somewhat boring data structure. They stand by our side when things are otherwise getting complicated. They do not bitch or complain. They just work.

Literature

Bitsets and many, many other interesting things are extensively covered in:

[1] “Hacker’s Delight, Second Edition”, Henry S. Warrren, Jr., Addison-Wesley