Bitset Operations

What Is a Bitset?

Early in my career, I was working on an embedded system with only 2 KB of RAM. I needed to track the state of 512 different sensor flags. Using an array of booleans — which in C takes 1 byte each — would consume 512 bytes, a quarter of available memory. A bitset using one bit per flag took only 64 bytes. That project taught me that the difference between a boolean array and a bitset is the difference between one byte per flag and one bit per flag — an 8x memory savings that compounds rapidly.

A bitset (also called a bit array or bit vector) is a data structure that stores a compact array of bits. Each bit represents a boolean value: 1 for true/set, 0 for false/clear. Bitsets support four fundamental operations: set (turn a bit on), clear (turn a bit off), toggle (flip a bit), and test (check a bit's value). These four operations map directly to bitwise operations on an underlying integer or byte array.

During a log analysis pipeline optimization, I replaced a Set<Integer> with a BitSet for tracking seen event IDs. The memory savings were significant — a BitSet for 10,000 possible IDs uses about 1.25 KB versus 40 KB for a HashSet — and membership checks were faster.

The Four Fundamental Operations

Set a Bit

Setting a bit means turning it to 1. The operation uses bitwise OR with a mask that has a single 1 at the target position. The mask is created by shifting 1 left by N positions: 1 << N. OR ensures the target bit becomes 1 while all other bits are preserved.

// Set bit at position N in a bitset
void bitset_set(uint32_t *bitset, int n) {
    bitset[n / 32] |= (1u << (n % 32));
}

// Concrete example: set bit at position 5
// bitset = 0000 0000 0000 0000 (before)
// bitset |= 1 << 5    0000 0000 0010 0000 (after)
// Bit 5 is now 1, all other bits unchanged

Clear a Bit

Clearing a bit means turning it to 0. The operation uses bitwise AND with the inverse mask. First, create the mask with a 1 at the target position, then invert it with NOT (~). The inverted mask has a 0 at the target position and 1s everywhere else. AND with this mask clears only the target bit.

// Clear bit at position N
void bitset_clear(uint32_t *bitset, int n) {
    bitset[n / 32] &= ~(1u << (n % 32));
}

// Concrete example: clear bit at position 5
// bitset = 0000 0000 0010 0000 (before)
// bitset &= ~(1 << 5)    0000 0000 0000 0000 (after)
// Bit 5 is now 0, all other bits unchanged

Toggle a Bit

Toggling a bit flips its value — 0 becomes 1, 1 becomes 0. The operation uses XOR with the mask. XOR has the property that x ^ 1 = ~x and x ^ 0 = x, so each call toggles exactly the target bit.

// Toggle bit at position N
void bitset_toggle(uint32_t *bitset, int n) {
    bitset[n / 32] ^= (1u << (n % 32));
}

// Concrete example: toggle bit at position 5 twice
// bitset = 0000 0000 0000 0000 (start)
// bitset ^= 1 << 5    0000 0000 0010 0000 (toggled ON)
// bitset ^= 1 << 5    0000 0000 0000 0000 (toggled OFF)
// XOR is its own inverse — toggle twice and you get back to original

Test a Bit

Testing a bit checks whether it is 1 or 0. The operation uses AND with the mask. If the result is non-zero, the bit is set. If zero, the bit is clear.

// Test bit at position N — returns 1 if set, 0 if clear
int bitset_test(const uint32_t *bitset, int n) {
    return (bitset[n / 32] >> (n % 32)) & 1u;
}

// Alternative (more common in production code):
#define BITSET_TEST(bitset, n) \
    ((bitset[(n) / 32] & (1u << ((n) % 32))) != 0)

Advanced Bitset Operations

Beyond the four fundamental operations, bitsets support powerful bulk operations on entire words. These are where bitsets really shine — performing set operations on 32 or 64 bits with a single CPU instruction.

Bulk Set Operations

// Bulk operations on an entire bitset (word by word)
void bitset_union(uint32_t *dest, const uint32_t *a, const uint32_t *b, int words) {
    for (int i = 0; i < words; i++)
        dest[i] = a[i] | b[i];   // OR — combine flags from both
}

void bitset_intersection(uint32_t *dest, const uint32_t *a, const uint32_t *b, int words) {
    for (int i = 0; i < words; i++)
        dest[i] = a[i] & b[i];   // AND — flags present in both
}

void bitset_difference(uint32_t *dest, const uint32_t *a, const uint32_t *b, int words) {
    for (int i = 0; i < words; i++)
        dest[i] = a[i] & ~b[i];  // AND NOT — flags in A but not in B
}

Finding the First Set Bit

Finding the lowest set bit is a common operation. Modern CPUs have a dedicated instruction called CTZ (Count Trailing Zeros) or BSF (Bit Scan Forward). When writing portable code, you can find it with a loop or use the De Bruijn sequence trick for O(1) lookups.

// Find position of first set bit using built-in function (GCC/Clang)
int bitset_find_first(const uint32_t *bitset, int totalBits) {
    for (int i = 0; i * 32 < totalBits; i++) {
        if (bitset[i] != 0) {
            return i * 32 + __builtin_ctz(bitset[i]);
        }
    }
    return -1; // no bits set
}

// Manual count-trailing-zeros using De Bruijn sequence (portable)
const int DE_BRUIJN[32] = {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
int ctz(uint32_t v) {
    return DE_BRUIJN[((v & -v) * 0x077CB531u) >> 27];
}

Real-World Bitset Usage

Operating System Page Tables

Linux uses a bitset called the page frame bitmap to track which physical memory pages are free or allocated. Each bit represents one 4 KB page. On a system with 32 GB of RAM, the page frame bitmap is exactly 1 MB (32 GB / 4 KB / 8 bits). The kernel allocates and frees pages by setting and clearing bits — operations that take nanoseconds.

Network Socket Event Monitoring

The select() system call uses bitsets (fd_set) to monitor multiple file descriptors. Users set bits in the read, write, and exception sets, then call select() to see which descriptors are ready. Each fd_set is a bitset of size FD_SETSIZE (typically 1024 bits). The kernel uses bitwise operations to compute the union of ready descriptors across all three sets.

Garbage Collection Marking

Many garbage collectors use a bitset to track which objects in the heap are "live" during mark-sweep collection. Each bit corresponds to one object slot. During the mark phase, the collector sets bits for reachable objects. During sweep, it clears bits and reclaims unmarked objects. The bitset is reset by clearing all bits — which is simply a memset to zero on the underlying byte array.

// Java-like garbage collector mark bitset
class MarkBitset {
    private long[] bits; // each long holds 64 bits

    void mark(int objectIndex) {
        bits[objectIndex >> 6] |= (1L << (objectIndex & 63));
    }

    boolean isMarked(int objectIndex) {
        return (bits[objectIndex >> 6] & (1L << (objectIndex & 63))) != 0;
    }

    void clearAll() {
        Arrays.fill(bits, 0L); // bulk zero — all bits cleared in one shot
    }
}