cbitset · A fast, tiny bitset library in C

Why cbitset

Small surface, serious speed

Everything you need to treat bits as a set — and nothing you don't.

📦

Tiny

Just three files — two headers and one source file. Drop it in and go.

⚡

Fast

Word-at-a-time set operations and trailing-zero iteration over 64-bit words.

✅

Tested

Continuously tested on Linux and Windows (MSYS2) across compilers.

🔧

Straight C

No dependencies, no C++. Portable C11 — works with MSVC, GCC and Clang.

Usage

Built for real work

Set operations, counts and iteration read just like the math.

1 Set operations on two bitsets

setops.c

bitset_t *a = bitset_create();
bitset_t *b = bitset_create();
for (int k = 0; k < 1000; ++k) bitset_set(a, 2 * k);
for (int k = 0; k < 1000; ++k) bitset_set(b, 3 * k);

// in-place: results land in `a`
bitset_inplace_union(a, b);
bitset_inplace_intersection(a, b);
bitset_inplace_difference(a, b);
bitset_inplace_symmetric_difference(a, b);

// counts without materializing the result
bitset_intersection_count(a, b);
bitset_union_count(a, b);

// predicates
bitsets_intersect(a, b);
bitsets_disjoint(a, b);
bitset_contains_all(a, b);

2 Fast iteration in batches

iterate.c

bitset_t *b = bitset_create();
for (int k = 0; k < 1000; ++k) bitset_set(b, 3 * k);

// one bit at a time
for (size_t i = 0; bitset_next_set_bit(b, &i); i++) {
    do_something(i);
}

// or decode many bits per call
size_t buffer[256];
size_t howmany = 0;
for (size_t from = 0;
     (howmany = bitset_next_set_bits(b, buffer, 256, &from)) > 0;
     from++) {
    for (size_t i = 0; i < howmany; i++)
        do_something(buffer[i]);
}

bitset_free(b);

Get started

Install in a minute

Build with CMake, vendor it directly, or use plain Makefiles.

Build & test with CMake

cmake -B build
cmake --build build
ctest --test-dir build

Install the library, headers & CMake package

cmake -B build
cmake --build build
cmake --install build   # add --prefix /path to relocate

Headers install under a cbitset subdirectory, so include them as #include <cbitset/bitset.h>.

Pull it into your own CMake project

include(FetchContent)
FetchContent_Declare(cbitset
  GIT_REPOSITORY https://github.com/lemire/cbitset.git
  GIT_TAG master)
FetchContent_MakeAvailable(cbitset)

target_link_libraries(myapp PRIVATE cbitset::cbitset)

Already installed? Find it with find_package(cbitset REQUIRED) and link cbitset::cbitset.

Old-school Makefile

make
./unit

Requires a C11-compatible compiler. Visual Studio supports C11/C17.

Reference

API at a glance

The full public interface from cbitset/bitset.h.

Lifecycle create / free

`bitset_t *bitset_create(void)`	Create a new empty bitset. Returns `NULL` on failure.
`bitset_t *bitset_create_with_capacity(size_t size)`	Create a bitset preallocated to hold `size` bits.
`bitset_t bitset_copy(const bitset_t b)`	Return an independent copy of a bitset.
`void bitset_free(bitset_t *b)`	Free all memory held by a bitset.

Bit access set / get

`void bitset_set(bitset_t *b, size_t i)`	Set bit `i` to one, growing the bitset if needed.
`void bitset_set_to_value(bitset_t *b, size_t i, bool v)`	Set bit `i` to the given boolean value.
`bool bitset_get(const bitset_t *b, size_t i)`	Return the value of bit `i`.
`void bitset_clear(bitset_t *b)`	Set every bit to zero.
`void bitset_fill(bitset_t *b)`	Set every bit to one.

Queries count / min / max

`size_t bitset_count(const bitset_t *b)`	Number of bits set to one (cardinality).
`bool bitset_empty(const bitset_t *b)`	True if no bit is set.
`size_t bitset_minimum(const bitset_t *b)`	Index of the first set bit, or `SIZE_MAX` if empty.
`size_t bitset_maximum(const bitset_t *b)`	Index of the last set bit, or zero if empty.
`size_t bitset_size_in_bits(const bitset_t *b)`	How many bits can currently be accessed.
`size_t bitset_size_in_bytes(const bitset_t *b)`	Memory used by the backing buffer, in bytes.
`size_t bitset_size_in_words(const bitset_t *b)`	Memory used by the backing buffer, in 64-bit words.

Set operations union / intersection / difference

In-place operations write the result into b1; copy first to keep the original.

`bool bitset_inplace_union(b1, b2)`	b1 ← b1 ∪ b2. Returns true on success.
`void bitset_inplace_intersection(b1, b2)`	b1 ← b1 ∩ b2.
`void bitset_inplace_difference(b1, b2)`	b1 ← b1 ∖ b2.
`bool bitset_inplace_symmetric_difference(b1, b2)`	b1 ← b1 △ b2. Returns true on success.
`size_t bitset_union_count(b1, b2)`	Size of the union without materializing it.
`size_t bitset_intersection_count(b1, b2)`	Size of the intersection without materializing it.
`size_t bitset_difference_count(b1, b2)`	Size of the difference.
`size_t bitset_symmetric_difference_count(b1, b2)`	Size of the symmetric difference.

Predicates relations

`bool bitsets_intersect(b1, b2)`	True if the bitsets share any element.
`bool bitsets_disjoint(b1, b2)`	True if the bitsets share no element.
`bool bitset_contains_all(b1, b2)`	True if b1 contains every set bit of b2.

Iteration traverse set bits

`bool bitset_next_set_bit(const bitset_t b, size_t i)`	Advance `*i` to the next set bit; returns false when exhausted.
`size_t bitset_next_set_bits(b, buffer, capacity, *from)`	Decode up to `capacity` set bits into `buffer`; returns the count.
`bool bitset_for_each(b, iterator, ptr)`	Call `iterator(value, ptr)` for each set bit; stops if it returns false.
`void bitset_print(const bitset_t *b)`	Print the set as `{a, b, c, }` to stdout.

Resizing advanced

`bool bitset_resize(b, newarraysize, padwithzeroes)`	Resize to `newarraysize × 64` bits, optionally zero-padding.
`bool bitset_grow(b, newarraysize)`	Grow capacity to `newarraysize × 64` bits with zero padding.
`bool bitset_trim(b)`	Release unused trailing memory.
`void bitset_shift_left(b, s)`	Shift every value up by `s` positions.
`void bitset_shift_right(b, s)`	Shift every value down by `s`; negatives are dropped.

Read the full header →

A fast, tinybitset library in C