# Why Bit Sets Matter

### Bit Sets

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

Each value has only two states:

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

A normal array of booleans is easy to understand:

```text
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.

```text
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:

```text
10,000 bits = 1,250 bytes
```

This is compact.

Bit sets are common in:

```text
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:

```text
{ 1, 3, 4 }
```

can be stored as bits:

```text
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:

```text
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:

```zig
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:

```zig
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:

```text
true
false
```

This line creates an empty set:

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

Empty means all bits are `0`.

```text
00000000...
```

Then:

```zig
set.set(3);
set.set(10);
```

turns on bit `3` and bit `10`.

## Checking a Bit

Use `isSet`:

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

This asks:

```text
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`:

```zig
set.unset(10);
```

Before:

```text
bit 10 = 1
```

After:

```text
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:

```text
0 becomes 1
1 becomes 0
```

If the API has `toggle`, it looks like:

```zig
set.toggle(3);
```

You can also express the idea manually with a check:

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

## Full and Empty Sets

You can create an empty set:

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

You can also create a full set:

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

A full set means every bit is present.

```text
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:

```zig
const n = set.count();
```

If the set contains:

```text
{ 1, 3, 4 }
```

then the count is:

```text
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:

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

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

For this set:

```text
{ 3, 10 }
```

the loop prints:

```text
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:

```zig
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:

```zig
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:

```zig
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:

```zig
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.

| Type | Size known when? | Allocates? | Good for |
|---|---:|---:|---|
| `IntegerBitSet(N)` | Compile time | No | Small sets, usually up to integer-sized storage |
| `StaticBitSet(N)` | Compile time | No | Fixed-size sets with many bits |
| `DynamicBitSet` | Runtime | Yes | Size decided while program runs |

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.

```zig
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:

```text
node 0 visited
node 3 visited
node 5 visited
```

This is compact and clear.

## Example: Permissions

A bit set can also represent permissions.

```text
0 = read
1 = write
2 = execute
```

If bits `0` and `1` are set:

```text
read = yes
write = yes
execute = no
```

Example:

```zig
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:

```text
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:

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

Union:

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

Intersection:

```text
A intersection B = { 3 }
```

Difference:

```text
A minus B = { 1, 2 }
```

Internally, these operations are bitwise operations.

```text
A: 0 1 1 1 0 0
B: 0 0 0 1 1 1
```

Union uses OR:

```text
0 1 1 1 1 1
```

Intersection uses AND:

```text
0 0 0 1 0 0
```

Difference uses AND with NOT:

```text
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:

```zig
var bits: u8 = 0;
```

has 8 bits:

```text
00000000
```

To set bit 3:

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

Now:

```text
00001000
```

To check bit 3:

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

To clear bit 3:

```zig
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:

```text
0 through 7
```

This is valid:

```zig
set.set(7);
```

This is invalid:

```zig
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`.

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

No cleanup is needed.

`DynamicBitSet` does allocate memory.

So it needs `deinit`.

```zig
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.

```text
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.