Why Bit Sets Matter

Bit Sets

A bit set is a compact collection of yes-or-no values.

Each value has only two states:

true or false
present or absent
enabled or disabled
visited or not visited

A normal array of booleans is easy to understand:

index:  0      1      2      3
value: true   false  true   false

But each boolean may take more space than one bit in memory.

A bit set stores each yes-or-no value as one bit.

bit:    0 1 2 3 4 5 6 7
value:  1 0 1 0 0 0 1 1

This makes bit sets useful when you need many flags.

Why Bit Sets Matter

Suppose you need to store whether each number from 0 to 9999 has been seen.

With a normal boolean array, you store 10,000 boolean values.

With a bit set, you store 10,000 bits.

That is roughly:

10,000 bits = 1,250 bytes

This is compact.

Bit sets are common in:

visited arrays
permissions
feature flags
compiler data-flow analysis
sets of small integer IDs
graph algorithms
sparse state tracking

They are especially useful when the possible values are small integer indexes.

The Basic Model

A bit set represents a set of integers.

For example, this set:

{ 1, 3, 4 }

can be stored as bits:

index: 0 1 2 3 4 5
bit:   0 1 0 1 1 0

A 1 means the value is present.

A 0 means the value is absent.

So:

bit 1 = present
bit 3 = present
bit 4 = present

Everything else is absent.

Zig Standard Library Bit Sets

Zig’s standard library provides bit set types in std.bit_set.

The exact names can vary slightly across Zig versions, but the common idea is:

const std = @import("std");
const BitSet = std.bit_set.IntegerBitSet(64);

This creates a bit set that can store indexes from 0 to 63.

It uses an integer internally.

That means it is very small and fast.

Creating an IntegerBitSet

Example:

const std = @import("std");

pub fn main() void {
    var set = std.bit_set.IntegerBitSet(64).initEmpty();

    set.set(3);
    set.set(10);

    std.debug.print("{}\n", .{set.isSet(3)});
    std.debug.print("{}\n", .{set.isSet(4)});
}

Output:

true
false

This line creates an empty set:

var set = std.bit_set.IntegerBitSet(64).initEmpty();

Empty means all bits are 0.

00000000...

Then:

set.set(3);
set.set(10);

turns on bit 3 and bit 10.

Checking a Bit

Use isSet:

if (set.isSet(10)) {
    std.debug.print("10 is present\n", .{});
}

This asks:

is bit 10 equal to 1?

If yes, the value is in the set.

If no, the value is not in the set.

Clearing a Bit

Use unset:

set.unset(10);

Before:

bit 10 = 1

After:

bit 10 = 0

This removes the value from the set.

Toggling a Bit

Some bit set types provide a way to toggle a bit.

Conceptually, toggling means:

0 becomes 1
1 becomes 0

If the API has toggle, it looks like:

set.toggle(3);

You can also express the idea manually with a check:

if (set.isSet(3)) {
    set.unset(3);
} else {
    set.set(3);
}

Full and Empty Sets

You can create an empty set:

var empty = std.bit_set.IntegerBitSet(64).initEmpty();

You can also create a full set:

var full = std.bit_set.IntegerBitSet(64).initFull();

A full set means every bit is present.

index: 0 1 2 3 4 5
bit:   1 1 1 1 1 1

For a 64-bit set, indexes 0 through 63 are all present.

Counting Set Bits

A useful operation is counting how many bits are set.

Depending on the type and Zig version, this may be exposed by a method such as count.

Conceptually:

const n = set.count();

If the set contains:

{ 1, 3, 4 }

then the count is:

3

This operation is usually very fast because CPUs have instructions for counting set bits.

Iterating Over Set Bits

Bit sets are often used when you want to visit only present indexes.

The idea looks like this:

var it = set.iterator(.{});

while (it.next()) |index| {
    std.debug.print("{}\n", .{index});
}

For this set:

{ 3, 10 }

the loop prints:

3
10

This is better than checking every possible index when the set is small compared with the maximum range.

StaticBitSet

When the number of bits is known at compile time but larger than one integer, Zig provides a static bit set style.

Conceptually:

var set = std.bit_set.StaticBitSet(1000).initEmpty();

This can store indexes from 0 to 999.

It stores the needed words internally.

Use it when the size is fixed at compile time.

Example:

const std = @import("std");

pub fn main() void {
    var visited = std.bit_set.StaticBitSet(1000).initEmpty();

    visited.set(42);

    if (visited.isSet(42)) {
        std.debug.print("visited\n", .{});
    }
}

This is useful for graph algorithms when the maximum number of nodes is known.

DynamicBitSet

Sometimes the number of bits is known only at runtime.

For that, use a dynamic bit set type.

Conceptually:

var set = try std.bit_set.DynamicBitSet.initEmpty(allocator, size);
defer set.deinit();

This allocates memory because the size is not known at compile time.

Example:

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var visited = try std.bit_set.DynamicBitSet.initEmpty(allocator, 10_000);
    defer visited.deinit();

    visited.set(1234);

    if (visited.isSet(1234)) {
        std.debug.print("visited 1234\n", .{});
    }
}

Use dynamic bit sets when the size comes from input, a file, a graph, or a command-line option.

IntegerBitSet vs StaticBitSet vs DynamicBitSet

The choice depends on size.

Start with the simplest type that fits your problem.

Example: Visited Nodes

Suppose we have graph nodes numbered from 0 to 7.

We can use a bit set to track which nodes were visited.

const std = @import("std");

pub fn main() void {
    var visited = std.bit_set.IntegerBitSet(8).initEmpty();

    visited.set(0);
    visited.set(3);
    visited.set(5);

    for (0..8) |i| {
        if (visited.isSet(i)) {
            std.debug.print("node {} visited\n", .{i});
        }
    }
}

Output:

node 0 visited
node 3 visited
node 5 visited

This is compact and clear.

Example: Permissions

A bit set can also represent permissions.

0 = read
1 = write
2 = execute

If bits 0 and 1 are set:

read = yes
write = yes
execute = no

Example:

const std = @import("std");

const Permission = enum(u3) {
    read = 0,
    write = 1,
    execute = 2,
};

pub fn main() void {
    var perms = std.bit_set.IntegerBitSet(8).initEmpty();

    perms.set(@intFromEnum(Permission.read));
    perms.set(@intFromEnum(Permission.write));

    if (perms.isSet(@intFromEnum(Permission.read))) {
        std.debug.print("can read\n", .{});
    }

    if (!perms.isSet(@intFromEnum(Permission.execute))) {
        std.debug.print("cannot execute\n", .{});
    }
}

Output:

can read
cannot execute

Enums make the meaning clearer than using raw numbers everywhere.

Set Operations

Bit sets are powerful because they can perform set operations quickly.

Suppose:

A = { 1, 2, 3 }
B = { 3, 4, 5 }

Union:

A union B = { 1, 2, 3, 4, 5 }

Intersection:

A intersection B = { 3 }

Difference:

A minus B = { 1, 2 }

Internally, these operations are bitwise operations.

A: 0 1 1 1 0 0
B: 0 0 0 1 1 1

Union uses OR:

0 1 1 1 1 1

Intersection uses AND:

0 0 0 1 0 0

Difference uses AND with NOT:

0 1 1 0 0 0

This is much faster than looping over ordinary sets one element at a time.

Manual Bit Operations

You can understand bit sets by looking at manual bit operations.

This integer:

var bits: u8 = 0;

has 8 bits:

00000000

To set bit 3:

bits |= (@as(u8, 1) << 3);

Now:

00001000

To check bit 3:

const is_set = (bits & (@as(u8, 1) << 3)) != 0;

To clear bit 3:

bits &= ~(@as(u8, 1) << 3);

You normally should use the standard library bit set types, but knowing the underlying operation helps.

A bit set is a friendly wrapper around this idea.

Bounds Matter

A bit set has a fixed range.

For IntegerBitSet(8), valid indexes are:

0 through 7

This is valid:

set.set(7);

This is invalid:

set.set(8);

Index 8 is outside the set.

Always make sure the index fits the bit set size.

Memory Ownership

IntegerBitSet and StaticBitSet do not allocate heap memory.

They are plain values.

So they do not need deinit.

var set = std.bit_set.IntegerBitSet(64).initEmpty();

No cleanup is needed.

DynamicBitSet does allocate memory.

So it needs deinit.

var set = try std.bit_set.DynamicBitSet.initEmpty(allocator, size);
defer set.deinit();

This follows the same Zig rule you have already seen:

If a type allocates, it usually needs cleanup.

Common Beginner Mistakes

The first mistake is using a bit set when the values are not small integer indexes. A bit set is good for values like 0, 1, 2, 3, not arbitrary strings.

The second mistake is using an index outside the valid range.

The third mistake is forgetting deinit for dynamic bit sets.

The fourth mistake is using raw bit operations everywhere when a standard bit set would be clearer.

The fifth mistake is forgetting that a bit set stores presence, not order. It can tell you whether 5 is present, but it does not remember when 5 was inserted.

A Useful Mental Model

A bit set is a row of switches.

index: 0 1 2 3 4 5
bit:   0 1 0 1 1 0

Switch on means present.

Switch off means absent.

The index is the value being tracked.

This is why bit sets are so compact: each value needs only one bit.

Summary

A bit set stores many yes-or-no values compactly.

Use it when your possible values are small integer indexes.

Use IntegerBitSet for small fixed-size sets.

Use StaticBitSet for larger fixed-size sets.

Use DynamicBitSet when the size is known only at runtime.

Bit sets are useful for visited flags, permissions, feature flags, compiler sets, graph algorithms, and fast set operations.